谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 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 索引结构做了一个铺垫,下期见。