【恶补知识点】动态查找树

重要提醒：本知识点几乎是必考无疑，无论是开发工程师还是数据工程师，如MySQL的innodb存储结构用的B+树，为何？

• 二叉搜索树（二叉排序树 or 二叉查找树）：或者是一棵空树，或者具有以下性质的二叉树：

1）若它的左子树不空，则左子树上所有结点的值均小于其根结点的值；

2）若它的右子树不空，则左子树上所有结点的值均大于其根结点的值；

3）它的左右子树也分别为二叉排序树。

其查找时间复杂度为 。

• 平衡二叉树（AVL树）：或者是一棵空树，或者具有以下性质的二叉树：

它的左右子树也分别为平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1；

其查找时间复杂度为 。

• B-树：是一种平衡的多路搜索树，适用于文件系统。

一棵 阶的 树或者是空树，或满足以下性质的 叉树：

1）树中每个节点至多有 棵子树；

2）若根节点不是叶子结点，则至少有两棵子树；

3）除根之外的所有非终端结点至少有 棵子树；

4）所有非终端结点包含以下的信息数据：

其中， 为关键字，； 为指向子树根结点的指针，且 所指子树中所有结点的关键字均小于 ， 所指子树中所有结点的关键字均大于 ；

5）所有的叶子结点都出现在同一层次上，并且不带信息（空指针）。

计算树的深度：

• B+树：B+树是应文件系统所需而出的一种B-树的变体，也是一种多路搜索树。

一棵 阶的 树与 的差异在于：

1）有n棵子树的结点含有n个关键字；

2）所有的叶子结点包含了全部关键字的信息及其指针，且叶子结点本身依关键字的大小自小而大链接；

3）所有非终端结点可以看作是索引部分，结点中仅含有其子树中的最小（或最大）的关键字。

B+树有两种查找运算：

1）从最小关键字起顺序查找；

2）从根结点开始，进行随机查找。

B+的特性：

1）所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2）不可能在非叶子结点命中；

3）非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4）更适合文件索引系统。

• B*树：是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。

B* 树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

• 键树（数字查找树）

是一棵度 的树，树中的每个结点中不包括一个或者几个关键字，而是只含有组成关键字的符号；

关键字中的各个符号分布在从根结点到叶子结点的路径上，叶子结点内的 $ 符号为结束标志符号，因此键树的深度与关键字的集合大小无关；

键树被约定为一棵有序树。

参考文献

• B树，B-树和B+树、B*树的区别