树形结构存储

㈠ 数据的存储结构可以用什么和什么

数据的存储结构可以用集合、线性结构、树形结构和图形结构，具体如下：

（1）集合：数据结构中的元素之间除了“同属一个集合”的相互关系外，别无其他关系；

（2）线性结构：数据结构中的元素存在一对一的相互关系；

（3）树形结构：数据结构中的元素存在一对多的相互关系；

（4）图形结构：数据结构中的元素存在多对多的相互关系。

常用运算：

（1）检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。

（2）插入。往数据结构中增加新的节点。

（3）删除。把指定的结点从数据结构中去掉。

（4）更新。改变指定节点的一个或多个字段的值。

（5）排序。把节点按某种指定的顺序重新排列。例如递增或递减。

以上内容参考：网络-数据结构

㈡ 树的存储表示是什么

树的存储结构根据应用的不同而不同，有的从双亲的角度考虑，引出了双亲表示法，有的从孩子的角度考虑，给出孩子表示法，还有的从孩子和兄弟的角度来讨论。这些都是人们在大量的应用中所使用的不同形式的存储结构，这里介绍常用的双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。

1.双亲表示法由树的定义可知，树中每个结点都有且仅有一个双亲结点，根据这一特性，可以用一组连续的一维数组来存储树中的各个结点（一般按层次存储），数组中的一个元素对应树中的一个结点，其中包括结点的数据信息以及该结点的双亲在数组中的下标。树的这种存储方法称为双亲表示法，双亲表示法的结点结构如图1所示，其中，data表示数据域，存储树中结点的数据信息，parent表示指针域，存储该结点的双亲在数组中的下标。

1.双亲表示法的存储结构2）双亲表示法示例图1所示的树的双亲表示如图1所示，这是一棵树及其双亲表示法的存储结构。根结点A无双亲，所以parent的值为－1，G、H和I的parent值为4，表示它们的双亲是下标为4的结点E。这种存储结构利用任一结点的双亲是唯一的性质，可以方便地直接找到任一结点的双亲结点，但求结点的孩子结点时需要扫描整个数组。

图1树的双亲表示法示例

㈢ MongoDB树形数据存储

树形结构的存储是一种非常典型的需求，例如菜单、省市区、栏目等等。

将树形结构的每个节点作为一行存储，每个节点保存父节点的指针(pid)。优点是简单易懂，插入梁纳修改比较简单。缺点是若要获取某个节点的所有子节点，将是一件非常恶心的事情。

在方式1中增加left和right，相当于btree的左竖渣旦右分支，分别存储左右分支节点的最大值和最小值。优点是查询一个节点的子节点容易，仅需做范围查询查询即可。缺点是由于树形结构存储在里面，增加或修改已存在的节点将可能产生连锁反应，操作复杂。

将整个树结构存成一个文档，文档结构即树形结构，简明余扰易懂。缺点是文档越来越大，对所有节点的修改都集中在此文档中，并发操作受限。

将每个节点的子节点保存起来，优点是结构简单查询子节点方便，缺点是查询父节点会表麻烦。

充分利用文档型存储 schema-less的优点，受限存储一个大的树形文档，再将每个节点的其他信息单独存储。优点是操作简单，结构上的操作可直接操作树形文档，数据上的操作仅需操作单条数据。缺点，对所有节点的修改都集中在此文档中，并发操作受限。

㈣ 如何在关系型数据库中存储树形结构

文中使用公司部门结构树作为栗子，要在mysql中存储这个公司部门结构树

邻接表想必大家都不陌生吧，用邻接表的关键是，在每个节点存储他的父节点的id。

在每一个部门信息中都存储了他的父节点id，parent_id字段

导入数据的过程就不说了，直接来看下数据吧：

这里使用常用的几种查询方式来看下这种方案的查询

可以通过parent_id做查询条件，可以快速查询到一个部门的直属下级部门

通过部门信息中的parent_id去查相应的父节点信息就可以快速实现

这种数据存储结构下，更新数据是比较方便快捷的，添加数据时直接找准父节点的id，组织部门变更时，也直接变更父id就好了，删除时候，看自己业务是否需要删除子节点这几种情况，

路径标的要点，就是每个节点存储根节点到该节点的路径，其实我觉得和别的几种方案可以共用

在每一个部门信息中都存储了他完整的路径，path字段

导入数据的过程就不说了，直接来看下数据吧：

使用路径表，通过path这个字段查询起来是比较困难的，一般都需要使用like，CONCAT函数、REPLACE函数等做字符串的处理逻辑，查询起来比较复杂，这里不做展示了，线上服务不建议使用这种方式，查询效率低会影响到服务性能，一般建议和邻接表方式统一使用，同时添加parent_id和path字段，parent_id用来查询，path用来查看节点完整的路径

这种数据存储结构下，更新数据是比较方便快捷的，添加数据时直接找准路径就好，组织部门变更时，也直接找准路径就好，删除时候，看自己业务是否需要删除子节点这几种情况，

Closure Table，网络直译过来叫闭合表，大多数人叫做闭包表，这种方案的要点是存储公司部门信息主表中，不存储节点关系的数据，使用另一张关系表来存储节点之间的关系，其中包含了任何两个有关系（上下级）节点的关联信息

公司部门信息主表，只需要存储部门的本身信息

主要包括三个字段

要点就是关系表的一条记录是一个上级节点、下级节点、与他们之间的路径距离。拿部门结构图来举例子

总公司-企划部的关系数据是：

总公司-大区A的关系数据是：

关系表中存储所有的节点路径信息，还用distance表示路径的距离，需要把树形结构中每两个节点之间的路径信息都维护进来。

数据存储的过程就拿导入总公司-门店A的过程做个示例。主表的数据存储就不说，说下关系中，存储部门结构的路径信息，总公司-门店A总共包含以下几条路径：

看到了么，是存储了所有总公司-门店A之间的路径信息

这里使用常用的几种查询方式来看下这种方案的查询

这种数据存储结构下，更新数据比较麻烦，因为他存储了两节点直接所有路径信息（包括中间节点的）