数据库存储目录结构简介

目录

一、概述

二、数据库存储目录结构

1、邻接表

2、进阶邻接表模型

3、改进的先序遍历模型

三、总结

---

一、概述

        存储目录结构（树）是一个常见的问题，有多种解决方案。方法主要有邻接表、进阶邻接列表、改进的前序树遍历、递归查询、枚举路径、嵌套集、闭包表等。本文主要介绍邻接表模型、进阶邻接列表模型和改进的先序树遍历模型。

二、数据库存储目录结构

1、邻接表

        我们将尝试的第一种也是最优雅的方法叫做“邻接表模型”或“递归方法”。这是一个很好的方法，因为你只需要一个简单的函数来遍历你的树。在我们的食品商店中，邻接表看起来像这样:

​         如你所见，在邻接表方法中，你保存了每个节点的“父节点”。我们可以看到‘Pear’是‘Green’的子，是‘Fruit’的子等等。根节点“Food”没有父值。为了简单起见，我使用“title”值来标识每个节点。当然，在真实的数据库中，您将使用每个节点的数字id。

2、进阶邻接表模型

        该法仅仅需要在邻接列表的基础上，添加path_key（search_key）字段，该字段存储从根节点到节点的标识路径。进阶连接表相比邻接表由于存储了节点标识路径，可以快速查询子节点。

 示例伪代码：

struct Node
{
 Node* leftChild;
 Node* rightChild;
 std::vector<int> vecPath;
}
void preOrder(Node*node,std::vector<int> &path,int & ic)
{
   if(node==NULL)
   {
    return;
    }

   ic++;
   path.push_back(ic);
   node->vecPath = path;

   preOrder(node->leftChild,path,ic);
   preOrder(node->rightChild,path,ic);
   
   ic--;
   
   path.erase(path.begin()+path.size()-1);//删除最后一个元素
   
}

查询节点A的所有子孙节点
SELECT*FROM node2 WHERE search_key LIKE'%0-%';

3、改进的先序遍历模型

        改进的先序遍历模型即按照先序遍历的方式式，给节点分配左右值，第1次到达该节点时，设置左值，第2次到达该节点，设置右值。

 示例伪代码：

struct Node
{
 Node* leftChild;
 Node* rightChild;
 int left;
 int right;
}
void preOrder(Node*node,int &ic)
{
   if(node==NULL)
   {
    return;
   }
   node->left=++ic;
   preOrder(node->leftChild);
   preOrder(node->rightChild);
   node->right=++ic;
}

三、总结

​         现在，您已经熟悉了在数据库中存储树的三种方式。三种方法各有利弊，邻接表较为简单，进阶连接表相比邻接表可以快速查询子节点，先序遍历模型功能强大但较为复杂。大家可以根据应用需要进行选择。

参考：

数据库树形结构存储方法的选择_CodeSerial的博客-CSDN博客_树状数据库结构存放

树结构如何在关系型数据库中存储_知春秋的博客-CSDN博客_关系数据库存储树

多级目录树（森林）的三种数据库存储结构介绍 - 百度文库