B树，B+树，B*树
2019-10-17 本文已影响0人
柳蒿
与二叉树，红黑树这样的树不同，B树，B+树，B*树是n叉树。
m阶B树的特性：
- 每一个节点最多存储的关键字[m/2+1,m-1]
- 每一个节点的孩子节点的个数[m/2,m]
- 根节点至少有两个子节点
- 每个节点包括m个指针（A0，A1，A2）和m-1个数据域（K0，K1，K2），指针k0表示小于关键字小于A0的记录，k1表示A0，A1之间的记录。
- 每个节点的子树中所有的节点值都小于根节点
- 数据分布在所有节点中，如果要遍历所有的数据，则需要进行一次中序遍历，耗时较长
- 在B树中的查找相当于在数据中进行一次二分搜索。
m阶B+树：
每个节点包括m个指针（A0，A1，A2）和m个数据域（K0，K1，K2），指针k0指向最小值数据为A0的一个链表。
在B树的基础上，所有的节点值都在叶子节点上，通常是一个叶子节点有多个值，用链表连接。
所有的叶子节点在同一层，每个叶子节点之间用链表链接起来。查找全部记录更加便捷。
m阶B*树：
是B+树的变体，在相同层的节点之间用链表连接。
小结
二叉搜索树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
B（B-）树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子节点。所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；
