25. 什么是 B-Tree 索引？

B-Tree 是为磁盘等外存储设备设计的一种平衡查找树。因此在讲 B-Tree 之前先了解下磁盘的相关知识。

  • 系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

  • InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB 存储引擎中默认每个页的大小为 16 KB，可通过参数 innodb_page_size 将页的大小设置为 4K、8K、16K ，在 MySQL 中可通过如下命令查看页的大小：

    mysql> show variables like 'innodb_page_size';

  • 而系统一个磁盘块的存储空间往往没有这么大，因此 InnoDB 每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小 16KB 。InnoDB 在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘 I/O 次数，提高查询效率。

B-Tree 结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组 [key, data] ，key 为记录的键值，对应表中的主键值，data 为一行记录中除主键外的数据。对于不同的记录，key值互不相同。

一棵 m 阶的 B-Tree 有如下特性：

艿艿：如果胖友对算法了解不对，可能对下面的各种数字关系不太能理解。最起码，要弄懂层级关系，以及每种节点存储的数据。

  1. 每个节点最多有 m 个孩子。
    • 除了根节点和叶子节点外，其它每个节点至少有 Ceil(m/2) 个孩子。
    • 若根节点不是叶子节点，则至少有 2 个孩子。
  2. 所有叶子节点都在同一层，且不包含其它关键字信息。
  3. 每个非叶子节点包含 n 个关键字信息（P0,P1,…Pn, k1,…kn）
    • 关键字的个数 n 满足：ceil(m/2)-1 <= n <= m-1
    • ki(i=1,…n) 为关键字，且关键字升序排序。
    • Pi(i=0,…n) 为指向子树根节点的指针。P(i-1) 指向的子树的所有节点关键字均小于 ki ，但都大于 k(i-1) 。

B-Tree 中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个 3 阶的 B-Tree：

25. 什么是 B-Tree 索引？ - 图1

B-Tree 的结构

  • 每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的 key 和三个指向子树根节点的 point ，point 存储的是子节点所在磁盘块的地址。两个 key 划分成的三个范围域，对应三个 point 指向的子树的数据的范围域。
  • 以根节点为例，key 为 17 和 35 ，P1 指针指向的子树的数据范围为小于 17 ，P2 指针指向的子树的数据范围为 [17~35] ，P3 指针指向的子树的数据范围为大于 35 。

模拟查找 key 为 29 的过程：

  • 1、根据根节点找到磁盘块 1 ，读入内存。【磁盘I/O操作第1次】
  • 2、比较 key 29 在区间（17,35），找到磁盘块 1 的指针 P2 。
  • 3、根据 P2 指针找到磁盘块 3 ，读入内存。【磁盘I/O操作第2次】
  • 4、比较 key 29 在区间（26,30），找到磁盘块3的指针P2。
  • 5、根据 P2 指针找到磁盘块 8 ，读入内存。【磁盘I/O操作第3次】
  • 6、在磁盘块 8 中的 key 列表中找到 eky 29 。

分析上面过程，发现需要 3 次磁盘 I/O 操作，和 3 次内存查找操作。由于内存中的 key 是一个有序表结构，可以利用二分法查找提高效率。而 3 次磁盘 I/O 操作是影响整个 B-Tree 查找效率的决定因素。B-Tree 相对于 AVLTree 缩减了节点个数，使每次磁盘 I/O 取到内存的数据都发挥了作用，从而提高了查询效率。