数据库-数据结构

一、B-树、B+树、B*树

搜索树：左子节点<节点<右子节点。
B-树：多路搜索树。
B+树：B-树的变体，更适用于文件系统，如mysql数据库。具体的，适合通过叶子节点的链指针进行区间查找。
B*树：B+树变体，提高了空间使用率$1/2\to 2/3$。
参考文章：一文详解 B-树，B+树，B*树

1 B-树

对于一颗m阶B-树(上图m=3)
特点：

1. 根节点至少有2个子节点，或者为空树。
2. 非叶子节点的子节点数k：$\lceil m/2\rceil \le k\le m$。当一个节点满了，分配一个新节点，把原节点一半的数据移动到新节点，并将该新节点加入到父节点中。此时改动只有该满的节点和其父节点。
3. 非叶子节点的关键字数j：$j=k-1$。
4. 叶子节点在同一层。
5. 对于某个节点的关键字K[1],K[2]…K[M-1]，K[i]<K[i+1]。
6. 对于某个非叶子节点的指针P[1],P[2]…P[M]，P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其他的P[i]指向关键字在范围(K[i],K[i+1])的子树。
7. 关键字分布在整棵树。
8. 搜索过程中可能在非叶子节点结束。时间复杂度等于一次二分查找。

2 B+树

对于一颗m阶B+树(上图m=3)
与B-树的不同：

1. 应文件系统所需的B-树变体。
2. 非叶子节点的关键字个数j：$j=k$。
3. 关键字不保存数据，仅用于索引。数据保存在叶子节点。
4. 对于某个非叶子节点的指针P[1],P[2]…P[M]，P[i]指向关键字在范围[K[i],K[i+1])的子树。
5. 所有叶子节点由一个链指针链接起来。
6. 关键字分布在叶子节点。
7. 搜索过程中得到叶子节点才结束。时间复杂度仍然等于一次二分查找。

3 B*树

对于一颗m阶B*树(上图m=3)
与B+树的不同：

1. 在非根非叶子节点的层增加了兄弟指针。
2. 非叶子节点的子节点数k：$\lceil 2m/3\rceil \le k\le m$，原先是$\lceil m/2\rceil \le k\le m$，提高了块的最低使用率。当一个节点满了，根据兄弟指针检查兄弟节点是否满了，未满则将一部分数据移动到兄弟节点；如果满了则分配一个新节点，把原节点和兄弟节点各自$1/3$的数据移动到新节点，并将该新节点加入到父节点中。此时改动有该满的节点、其父节点、兄弟节点、兄弟指针。