B+

B+树

B+树是B树的变体，常用于数据库和操作系统的文件系统中，如MySQL数据库的索引就是基于B+树实现的

B+树的特点：

• 分为内部节点（非叶子）、叶子节点2种节点
  • 内部节点只存储key，不存储具体数据
  • 叶子节点存储key和具体数据
• 所有的叶子节点形成一条有序链表
• m阶B+树非根节点的元素数x
  • ┌ m/2 ┐ ≤ x ≤ m

对比B树，B+树的优势是:

• 每个节点存储的key数量更多，树的高度更低
• 所有的具体数据都存在叶子节点上，所以每次查询都要查到叶子节点，查询速度比较稳定
• 所有的叶子节点构成了一个有序链表，做区间查询时更方便

B*树

B*树是B+树的变体：给内部节点增加了指向兄弟节点的指针

• m阶B树非根节点的元素数量 x
• ┌ 2m/3 ┐ ≤ x ≤ m