B树

定义及性质

  • 对于一个m阶的B树

    • 每个结点最多有m-1个关键字和m个孩子指针

  • 根结点最小可以有1个关键字

    • 非根结点至少有$\lceil m/2\rceil-1$个关键字

  • 对于一个有n个关键字的结点

    • 每个结点的n个关键字以非降序排列
    • 每个结点的n+1个孩子指针
    • 对于一个指针,其左关键字为$key_{i}$,其右关键字为$key_{i+1}$,如果它不为null,那么该指针指向的结点的所有key都大于关键字$key_{i}$,且小于关键字$key_{i+1}$

  • 每个叶子结点具有相同的深度.

B+树

定义及性质

  • 对于一个m阶的B+树
    • 每个结点最多有m个关键字和m个孩子指针
  • 对于非叶子结点,结点内部不存储数据,只存储索引
  • 叶子结点存储了所有数据,同时满足非降序排序

带顺序访问指针

该B+树为每个叶子结点增加了一个指向相邻结点的指针

树的高度

假设有N个结点,对于一个M阶的B树

  1. 假设所有结点的关键字个数达到上限M-1,那么这时树的高度H满足$M^H=N$,因此$H=\log_M{N}$
  2. 假设所有结点的关键字个数达到下限$\lceil M/2\rceil-1$,近似取M/2,同理第一点,得到$H=\log_{M/2}{N}$

使用B/B+树的原因

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

性能分析:

由树的高度我们得知,B树的高度由M影响.而普通的二叉树如红黑树,其高度是$\log{N}$,对比B树,性能相差巨大.尤其是M越往大取.

再看为什么选择B+树而不是B树.

首页B+树的最大一个区别在于B+树的非叶子结点放弃了数据,只存储索引.这一变化带来的好处有:

  1. 进一步的降低了磁盘的读写.为什么呢?首页数据库设计将一个结点的大小作为磁盘的一页.在放弃了数据后,一页也就是一个结点能存放的索引更大了.
  2. 查找效率更加稳定.所有的数据都在叶子结点,因此每个查找的路径长度都为树的高度.
  3. B树因为每个结点都存放了数据,因此其产生了一个新的效率问题.遍历效率低.为此B+树将所有数据存放在叶子结点,遍历只需遍历叶子结点即可.而且数据库使用的B+树还在经典B+树上做了进一步的优化,为所有的叶子结点添加了指针.该做法提高了区间访问的性能.