B+ 树

B+树是B树的变体，常用于数据库与操作系统的文件系统中

• MySQL 数据库的 索引 就是基于 B+树 实现的

B+树的特点

• 分为 内部节点（非叶子）、叶子节点 两种节点
  • 内部节点（非叶子）：只存储 key，不存储具体数据
  • 叶子节点：存储 key 和 value
• 所有的 叶子节点 会形成一条 有序链表
• m 阶 B+ 树非根节点的元素数量为 x
  • 则满足 向下取整(m/2) ≤ x ≤ m
  • 直观解释：
    • B树：某个节点里面有 3 个元素，那么这个节点一般有 4 个子节点，因为它能分出 4 个叉
    • B+树：某个节点里面有 3 个元素，那么这个节点一般就有 3 个子节点

MySQL底层索引为何使用 B+ 树

• 为了减少IO操作次数，一般把一个节点的大小设计成最小读写单位的大小，与操作系统IO实现与物理IO实践相匹配
  • MySQL的存储引擎InnoDB的最小读写单位是 16KB
  • 为了做到这一点，就会在一个节点里，放非常多的元素
  • 由于树中存储的是 Key-Value 类型的数据，而在数据库场景下，value 本身是比较大的，采用 B树 则每个节点都会存储 value，使得单个节点能够存储的元素数目下降
• 对比 B树，B+树 的优势是：
  • 每个非叶子节点存储的 key 数量更多，意味着每个节点的分支也更多，树的高度更低
  • 所有具体数据都存储在叶子节点上，所以每次查询都要到达叶子节点，查询速度比较稳定
  • 所有叶子节点构成一个 有序链表，做区间查询更加方便；对于 B树 则需要使用树的中序遍历

B* 树

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

• m 阶 B* 树的非根节点元素数量为 x，则满足 向下取整(2m/3) ≤ x ≤ m