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

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

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

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

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

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

其查找时间复杂度为 $O(logn)$ 。

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

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

其查找时间复杂度为 $O(logn)$ 。

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

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

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

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

3）除根之外的所有非终端结点至少有 $⌈m/2⌉$ 棵子树；

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

$(n,A_0,K_1,A_1,K_2,A_2,\dots,K_n,A_n)$

其中， $K_i$ 为关键字， $K_i<K_{i+1}$ ； $A_i$ 为指向子树根结点的指针，且 $A_{i-1}$ 所指子树中所有结点的关键字均小于 $K_i$ ， $A_{i}$ 所指子树中所有结点的关键字均大于 $K_i$ ；

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

计算树的深度： $H \le {log}_{⌈m/2⌉}((N+1)/2)+1$

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

一棵 $m$ 阶的 $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+树要低，空间使用率更高。