查看“树：B*树”的源代码

[[category:数据结构]]

== 关于 ==
B*树 是“[http://wiki.eijux.com/%E6%A0%91%EF%BC%9AB%2B%E6%A0%91 B+树]”的变体，在“B+树”的基础上（叶子结点中包含全部关键字信息，及指向含有这些关键字记录的指针）：
# B*树 增加了'''非根非叶子结点指向兄弟的指针'''；
# B*树 定义了非叶子结点'''关键字个数至少为“2m/3”'''，即：块的最低使用率为“'''2/3'''”。【不同于“B+树”及“B树”的“'''1/2'''”】

: [[File:B＊树：典型结构.png|600px]]

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