考研计算机 b+树数据库索引 一张数据页能存储多少个索引节点

先从数据结构的角度来答。题主应该知道B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。这就决定了B+树更适合用来存储外部数据，也就是所谓的磁盘数据。从Mysql（Inoodb）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。那么Mysql如何衡量查询效率呢？磁盘IO次数，B-树（B类树）的特定就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，当查询数据的时候，最好的情况就是很快找到目标索引，然后读取数据，使用B+树就能很好的完成这个目的，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时啊！），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。另一个优点是什么，B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。至于MongoDB为什么使用B-树而不是B+树，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以Json格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，上面所述的优点2需求就没那么强烈了，其次Mysql由于使用B+树，数据都在叶节点上，每次查询都需要访问到叶节点，而MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql（但侧面来看Mysql至少平均查询耗时差不多）。总体来说，Mysql选用B+树和MongoDB选用B-树还是以自己的需求来选择的。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名申请、虚拟主机、营销软件、网站建设、上街网站维护、网站推广。

树的存储表示是什么？

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

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

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

图1树的双亲表示法示例

【数据结构】树的定义和树的三种存储结构

树（Tree）是n（n=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：

假设以一组连续空间存储数的结点，同时在每个结点中， 附设一个指示器指示其双亲结点到链表中的位置 。

把每个结点的孩子结点排列起来，以 单链表作为存储结构 ，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后 n个头指针又组成一个线性表，采用顺序存储结构 ，存放进一个一维数组中。

孩子表示法有两种结点结构： 孩子链表的孩子结点 和 表头数组的表头结点

对于孩子表示法，查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。但是 当要寻找某个结点的双亲时 ，就不是那么方便了。所以可以将双亲表示法和孩子表示法结合，形成 双亲孩子表示法 。

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟存在也是唯一的。因此，设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

怎样在 MySQL 表中存储树形结构数据

怎样在 MySQL 表中存储树形结构数据

一般比较普遍的就是四种方法：（具体见 SQL Anti-patterns这本书）Adjacency List：每一条记录存parent_idPath Enumerations：每一条记录存整个tree path经过的node枚举Nested Sets：每一条记录存 nleft 和 nrightClosure Table：维护一个表，所有的tree path作为记录进行保存。

怎样在 mysql 表中存储树形结构数据

解决方法很多!数据要存储为树形结构，那么数据要有父子关系。 一个父节点有多个子节点，一个子节点又有多个子子节点。 publicclassTreeNode{ /**节点主键**/ privateStringid; /**节点名称**/ privateStringtext; /**子节点**/ privateTreeNode[]children; }

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

文中使用公司部门结构树作为栗子，要在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之间的路径信息

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

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

当前标题：树结构存储nosql,树的存储结构
分享地址：http://scyanting.com/article/hdsoco.html