BTree 与 B+Tree

其实在之前的文章说说到过 MySQL 索引,只不过没细说,《JOIN 查询与索引简介》 ,现在来看看回顾一下索引相关的数据结构,首先看看索引的定义: 索引 (Index) 是帮助 MySQL 高效获取数据的数据结构。 我不会索引就是类似于字典这样的话泛泛而谈,而是如何真正去理解索引。

img

根据列字段信息的特点,去用一种数据结构存储这些特点,这就是索引,如上图:我们需要把第二列的值通过二叉查找树存储起来,每一个节点都是以 Key-Vlaue 的形式存在,把值当做 Key,把物理地址当做 Value,那么只要根据二叉查找树的特性,很快就可以找到对应的物理地址,从而取出数据。

数据库常见的索引有 Btree、B+tree、Hash 索引等等,今天主要探讨的是 BTree 和 B+Tree

B Tree

先看看 Btree 的定义:

  • 根节点至少包括两个孩子
  • 树中每个节点最多含有 m 个孩子 ( m>=2 )
  • 除根节点和叶节点外,其他每个节点至少有 ceil (m/2) 个孩子,这里的 ceil 是取上限的意思
  • 所有叶子节点位于同一层

假设每个非终端结点中包含有 n 个关键字信息,其中

  • Ki (i=1..n) 为关键字,且关键字按顺序升序排序 K (i-1) < Ki
  • 关键字的个数 n 必须满足: [ceil (m / 2) -1] <= n <= m-1
  • 非叶子结点的指针: P [1],P [2],… P [M];其中 P [1] 指向关键字小于 K [1] 的子树,P [M] 指向关键字大于 K [M-1] 的子树,其它 P [i] 指向关键字属于 (K [i-1],K [i]) 的子树

看起来是非常绕的,通过下面的图示其实是蛮好懂的:

mark

由于 B-Tree 的特性,在 B-Tree 中按 key 检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的 data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到 null 指针,前者查找成功,后者查找失败。

但是由于插入删除新的数据记录会破坏 B-Tree 的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持 B-Tree 性质,在这里先不讨论插入删除新的数据记录的问题。

B+Tree

B + 树是 B 树的变体, B-Tree 有许多变种,其中最常见的是 B+Tree,例如 MySQL 就普遍使用 B+Tree 实现其索引结构。 B + 树的定义基本与 B 树相同,除了:

  • 非叶子节点的子树指针与关键字个数相同
  • 非叶子节点的子树指针 P [i],指向关键字值 [K [i],K [i+1]) 的子树
  • 非叶子节点仅用来作为索引,数据都保存在叶子节点中
  • 所有叶子节点均有一个链指针指向下一个叶子结点

mark

B+Tree 更适合做索引

1、B+Tree 的磁盘读写代价更低

B+Tree 内部并没有指向关键字具体信息的指针,也就是不存放数据,只存放索引信息,所能容纳的关键字数量也就越多,一次性读入内存需要查找的关键字也就越多,相对来说 IO 读写次数也就降低了

2、B+Tree 的查询效率更加稳定

由于 B+Tree 内部节点并不是直接指向文件内容的节点,而只是叶子节点中关键字的索引,所以任何关键字的查找必须走一条从根节点到叶子节点的路,所有关键字查询的路径长度相同,导致每一个数据的查询效率也几乎是相同的,所以查询效率更稳定

3、B+Tree 更有利于对数据库的扫描

B Tree 在提高了磁盘 IO 性能的同时,并没有解决元素遍历的效率底下的问题,而 B+Tree 只需要遍历叶子节点就可以解决对全部关键字信息的扫描,所以对于数据库频繁使用的范围查询是非常有利的

这也就是选择 B+Tree 作为主流索引数据结构的原因

Hash 索引

有些数据库存储引擎还支持 Hash 这个数据结构作为其索引哈希结构,想必大家已经非常熟悉了,就是根据哈希函数的运算,那只需经过一次定位便能找到需要的数据,相比起 B+Tree 索引,需要从根节点到非叶子节点,再到叶子节点才能访问到我们需要的数据,这样可能会经过多次的 IO 访问,所以呢,哈希索引的查询效率理论上要高于 B+Tree 索引。

mark

但是 Hash 也是有非常明显的缺点的:

1、仅仅能满足 “=” 、“IN”,不能使用范围查询

2、无法被用来避免数据的排序操作

3、不能利用部分索引建来查询

4、不能避免表扫描

5、遇到大量 Hash 值相等的情况后性能并不一定就会比 B-Tree 索引高