第15期：索引设计（索引组织方式 B+ 树）

谈到索引，大家并不陌生。索引本身是一种数据结构，存在的目的主要是为了缩短数据检索的时间，最大程度减少磁盘 IO。

任何有数据的场景几乎都有索引，比如手机通讯录、文件系统（ext4\xfs\ntfs)、数据库系统（MySQL\Oracle）。数据库系统和文件系统一般都采用 B+ 树来存储索引信息，B+ 树兼顾写和读的性能，最极端时检索复杂度为 O(logN)，其中 N 指的是节点数量，logN 表示对磁盘 IO 扫描的总次数。

MySQL 支持的索引结构有四种：B+ 树，R 树，HASH，FULLTEXT。

本篇简单介绍下 B+ 树，下一篇讲 MySQL 常用的两种引擎 MyISAM 和 InnoDB 的 B+ 树索引实现，其余的后面会讲到。

一、什么是二叉树？

再讲什么是 B+ 树之前，先来了看下什么是二叉树。

树本身是一种数据存储结构，因为类似现实生活中的树而命名。

一个看似没有修剪过的树，其实这是一棵二叉树，每个节点最多有两个子节点。

树相关的基础概念：

拿图 1 这棵树举例说明：

• 根节点：6 为根节点，根节点没有父节点，有儿子节点，一般叫做 ROOT 节点；
• 儿子节点：8 和 4 是 6 的儿子节点，4 是左儿子，8 是右儿子；
• 父节点：6 是 4 和 8 的父节点，父节点是儿子节点的上层节点；
• 叶子节点：4 和 5 是叶子节点，叶子节点指的是除根节点外没有儿子的节点；
• 兄弟节点：8 和 4 互为兄弟节点，因为有共同的父亲 6。10，9，7 三个节点没有兄弟，都只有一个儿子；
• 层数：一棵树的节点层数。图 1 层数为 6；
• 高度：自下向上遍历，从叶子节点遍历到根节点所需要的节点数量。叶子节点 5 到根节点遍历 7，9，10，8，6，这棵树的高度为 5；
• 深度：自上而下遍历，从根节点到叶子节点遍历所需要的节点数量，同样，这棵树的深度也是 5；
• 高度和深度一般以 0 开始计算，当然也有按照从 1 开始计算的；
• 平衡因子：某节点的左子树与右子树深度的差值，一般结果为绝对值。 如果任何一个子树不存在，按照 0 处理。比如节点 10 的平衡因子就是 3；

图 1 是一颗非常普通的树，非常容易退化为一张链表。如果把图 1 换成如下图， 根节点就变为 4，6 退化为 4 的儿子节点，这棵树就退化为一张链表。

链表的查找非常慢，只能按照节点顺序查找，每个节点都遍历一遍，时间复杂度为 O(n)，无法随机查找。

二、平衡二叉树（AVL）

那对图 1 进行下改造，把数据重新节点重新连接下，图 2 如下：

图 2 可以看到以下特性：

1. 所有左子树的节点都小于其对应的父节点（4，5，6）<（7）；（4）<（5）；（8）< （9）；

2. 所有右子树上的节点都大于其对应的父节点（8，9，10）>（7）；（6）>（5）；（10）>（9）；

3. 每个节点的平衡因子差值绝对值 <=1；

4. 每个节点都符合以上三个特征。

满足这样条件的树叫平衡二叉树（AVL）树。

问：那再次查找节点 5，需要遍历多少次呢？

由于数据是按照顺序组织的，那查找起来非常快，从上往下找：7-5，只需要在左子树上查找，也就是遍历 2 次就找到了 5。假设要找到叶子节点 10，只需要在右子树上查找，那也最多需要 3 次，7-9-10。也就说 AVL 树在查找方面性能很好，最坏的情况是找到一个节点需要消耗的次数也就是树的层数， 复杂度为 O(logN)

如果节点非常多呢？假设现在有 31 个节点，用 AVL 树表示如图 3：

图 3 是一棵高度为 4 的 AVL 树，有 5 层共 31 个节点，橙色是 ROOT 节点，蓝色是叶子节点。对 AVL 树的查找来看起来已经很完美了，能不能再优化下？比如，能否把这个节点里存放的 KEY 增加？能否减少树的总层数？那减少纵深只能从横向来想办法，这时候可以考虑用多叉树。

三、B 树

B 树是一种多叉的 AVL 树。B-Tree 减少了 AVL 数的高度，增加了每个节点的 KEY 数量。

B 树的特性：（m 为阶数：结点的孩子个数最大值）

1. 树中每个节点最多含有 m 个孩子节点 (m>=2)；

2. 除根节点和叶子结点外，其他节点的孩子数量 >=ceil(m / 2)；

3. 若根节点不是叶子结点，最少有两个孩子

• 特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点；

4. 每个非叶子结点中包含有 n 个关键字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn) 其中：

• Ki (i=1...n) 为关键字，且关键字按顺序升序排序 K(i-1)< Ki
• Pi 为指向儿子节点的指针，且指针 P(i-1) 指向的儿子节点里所有关键字均小于 Ki，但都大于 K(i-1)
• 关键字的个数 n 必须满足：[ceil(m / 2)-1]<= n <= m-1
• 如果一个结点有 n 个关键字，那么该结点有 n+1 个分支。这 n+1 个关键字按照递增顺序排列
• 所有叶子结点都出现在同一层，是所有遍历的终点位置

按照这个要求，把图 3 简单变为一棵 B 树，见图 4：

图 4 是一棵 4 阶 B 树，总共有 11 个节点，节点数比图 3 少了 20 个；层数为 3，比图 3 少了两层。实际应用中，每个最小单元不是 KEY，而一般是按照块（BLOCK）来算。比如磁盘文件系统 EXT4 每块 4KB；数据库比如 PostgreSQL 是 8KB，MySQL InnoDB 是 16KB， MySQL NDB 是 32KB 等。

所以再次理清图 4 的 B 树，变为图 5：

图 5 每个节点的基本单元是一个磁盘块（BLOCK，默认 4KB），根节点含有一个键值，其他节点含有 3 个键值，每个磁盘块包含对应的键值与数据。

比如现在要读取 KEY 为 31 的记录：先找到根节点磁盘块（1），读入内存。（第一次 IO）；关键字 31 大于区间（16，），根据指针 P2 找到磁盘块 3，读入内存（第二次 IO）；31 大于区间（20，24，28），根据指针 P4 读取磁盘块 11（第三次 IO），在磁盘块 11 中找到 KEY 为 31 的记录，返回结果。这期间有三次磁盘 IO 的读取。可以明确看到，B 树相对于 AVL 树，减少了树的节点数与树的深度，减少了磁盘 IO。

看到这里其实有一个问题，三次 IO，前两次 IO 其实从磁盘读取了不必要的数据，因为只用比较 KEY，所以非叶子节点对应的 DATA 完全没有必要，如果 DATA 很大，那完全是浪费内存资源。考虑下能否把非叶子节点的 DATA 拿掉？

四、B+ 树

B+ 树是对 B 树的一个小升级。大部分数据库的索引都是基于 B+ 树存储的。MySQL 的 MyISAM 和 InnoDB 引擎的索引都是基于 B+ 树存储。

B+ 树最大的几个特点：

1. 非叶子节点只保留 KEY，放弃 DATA；

2. KEY 和 DATA一起，在叶子节点，并且保存为一个有序链表（正序，反序，或者双向）；

3. B+ 树的查找与 B 树不同，当某个结点的 KEY 与所查的 KEY 相等时，并不停止查找，而是沿着这个 KEY 左边的指针向下，一直查到该关键字所在的叶子结点为止。

那对图 5 的 B 树做一个调整，变为以下 B+ 树，见图 6：

图 6 是一棵 6 阶 B+ 树。不同于图 5，非叶子节点不再包含除了主键外的数据，数据全部放在叶子节点，并且所有叶子节点存放在一个单向链表里，当然也可以双向链表。可以看到，B+ 树同时具有平衡多叉树和链表的优点，即可兼顾 B 树对范围查找的高效，又可兼顾链表随机写入的高效， 这也是大部分数据库都用 B+ 树来存储索引的原因。

本篇是为了下一篇介绍 MySQL 的两种常用引擎：MyISAM 和 InnoDB 索引结构做了一个铺垫，下期见。