数据库索引——B+树索引

索引是一种数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。
索引最形象的比喻就是图书的目录了。注意这里的大量，数据量大了索引才显得有意义

索引在 MySQL 数据库中分三类：

B+ 树索引
Hash 索引
全文索引

B+树索引

B+树进化具有的优点：

索引节点没有数据，比较小，能够完全加载到内存中
而且叶子节点之间都是链表的结构，所以B+Tree也是可以支持范围查询的，而B树每个节点key和data在一起，则无法区间查找
B+树中因为数据都在叶子节点，每次查询的时间复杂度是稳定的，因此稳定性保证了

为什么MySQL要使用B-Tree（B+Tree）? 有哪些优势？

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

（0）先看看数据库表的存储结构

MySQL的存储结构

表存储结构

单位：表>段>区>页>行

在数据库中，不论读一行，还是读多行，都是将这些行所在的页进行加载。也就是说存储空间的基本单位是页。
一个页就是一棵树B+树的节点，数据库I/O操作的最小单位是页，与数据库相关的内容都会存储在页的结构里。

B+树索引结构

在一棵B+树中，每个节点为都是一个页，每次新建节点的时候，就会申请一个页空间
同一层的节点为之间，通过页的结构构成了一个双向链表
非叶子节点为，包括了多个索引行，每个索引行里存储索引键和指向下一层页面的指针
叶子节点为，存储了关键字和行记录，在节点内部（也就是页结构的内部）记录之间是一个单向的链表

B+树页节点结构

有以下几个特点

将所有的记录分成几个组，每组会存储多条记录，
页目录存储的是槽（slot），槽相当于分组记录的索引，每个槽指针指向了不同组的最后一个记录
我们通过槽定位到组，再查看组中的记录

页的主要作用是存储记录，在页中记录以单链表的形式进行存储。
单链表优点是插入、删除方便，缺点是检索效率不高，最坏的情况要遍历链表所有的节点。因此页目录中提供了二分查找的方式，来提高记录的检索效率。

B+树的检索过程

我们再来看下B+树的检索过程

从B+树的根开始，逐层找到叶子节点。
找到叶子节点为对应的数据页，将数据叶加载到内存中，通过页目录的槽采用二分查找的方式先找到一个粗略的记录分组。
在分组中通过链表遍历的方式进行记录的查找。

（1）B+树的演变

二叉查找树（二叉搜索树）：不平衡

我们为 user 表（用户信息表）建立了一个二叉查找树的索引。

图中的圆为二叉查找树的节点，节点中存储了键（key）和数据（data）。键对应 user 表中的 id，数据对应 user 表中的行数据。

特点：

二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。

示例：

如果我们需要查找 id=12 的用户信息，利用我们创建的二叉查找树索引，查找流程如下：

将根节点作为当前节点，把 12 与当前节点的键值 10 比较，12 大于 10，接下来我们把当前节点>的右子节点作为当前节点。
继续把 12 和当前节点的键值 13 比较，发现 12 小于 13，把当前节点的左子节点作为当前节点。
把 12 和当前节点的键值 12 对比，12 等于 12，满足条件，我们从当前节点中取出 data，即 id=12，name=xm。

平衡二叉树（AVL树）：旋转耗时

利用二叉查找树可以快速的找到数据。但是，如果上面的二叉查找树是下面的构造，则二叉查找树变成了一个链表。如果我们需要查找 id=17 的用户信息，我们需要查找 7 次，也就相当于全表扫描了。 ——于是我们就有了平衡二叉树

特点：

平衡二叉树又称 AVL 树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过 1。

平衡二叉树和非平衡二叉树的对比：

当不平衡时，则需要调整二叉平衡树的平衡，请参考链接：AVL和红黑树的一些概念

红黑树：树太高

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

从实现来看，红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一，且节点颜色的划分需要满足特定的规则。

红黑树是满足如下条件的二叉搜索树：

每个结点要么是红色，要么是黑色
根节点是黑色
每个叶结点（NIL结点，空结点）是黑色的
不能有相邻的两个红色结点
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

红黑树示例如下：

与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。

但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。总的来说，红黑树的统计性能高于AVL。

因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。

对于数据在内存中的情况（如上述的TreeMap和HashMap），红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严重影响性能。

B树：为磁盘而生

为什么要从AVL树变成B树？

因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。

但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。

另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。

如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。

如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。

我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？

可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低！

因为数据库是要存储海量数据的，AVL树每个节点只储存一个键值和数据，并且数据是存储在磁盘上，当我们存储一个键值和数据，则速度会很慢，应该减少从磁盘读取数据的次数。当我们使用AVL树，树的高度极高，会进行很多次的磁盘IO，查找数据的效率会降低！

为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。

B树——平衡树

图中的 p 节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。

图中的每个节点称为页，页就是我们上面说的磁盘块，在 MySQL 中数据读取的基本单位都是页，所以我们这里叫做页更符合 MySQL 中索引的底层数据结构。

从上图可以看出，B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的 B 树为 3 阶 B 树，高度也会很低。

基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。

示例：

假如我们要查找 id=28 的用户信息，那么我们在上图 B 树中查找的流程如下：

先找到根节点也就是页 1，判断 28 在键值 17 和 35 之间，那么我们根据页 1 中的指针 p2 找到页 3。
将 28 和页 3 中的键值相比较，28 在 26 和 30 之间，我们根据页 3 中的指针 p2 找到页 8。
将 28 和页 8 中的键值相比较，发现有匹配的键值 28，键值 28 对应的用户信息为（28，bv）。

应用：B树在数据库中有一些应用，如mongodb的索引使用了B树结构。但是在很多数据库应用中，使用了是B树的变种B+树。

B+树

根据上图我们来看下 B+ 树和 B 树有什么不同：

① B+ 树非叶子节点上是不存储数据的，仅存储键值，而 B 树节点中不仅存储键值，也会存储数据。

之所以这么做是因为在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。

如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。

另外，B+ 树的阶数是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。

一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO。

② 因为 B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。

那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而 B 树因为数据分散在各个节点，要实现这一点是很不容易的。

B+ 树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。

其实上面的 B 树我们也可以对各个节点加上链表。这些不是它们之前的区别，是因为在 MySQL 的 InnoDB 存储引擎中，索引就是这样存储的。

也就是说上图中的 B+ 树索引就是 InnoDB 中 B+ 树索引真正的实现方式，准确的说应该是聚集索引（聚集索引和非聚集索引下面会讲到）。

通过上图可以看到，在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

MyISAM 中的 B+ 树索引实现与 InnoDB 中的略有不同。在 MyISAM 中，B+ 树索引的叶子节点并不存储数据，而是存储数据的文件地址。

为什么B+树比B树更适合数据库索引？

**B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，**B+树只需要去遍历叶子节点就可以实现整棵树的遍历，而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

B+树与B树的不同：

B+树非叶子节点不存在数据只存索引，B树非叶子节点存储数据
B+树查询效率更高。B+树使用双向链表串连所有叶子节点，区间查询效率更高（因为所有数据都在B+树的叶子节点，扫描数据库只需扫一遍叶子结点就行了），但是B树则需要通过中序遍历才能完成查询范围的查找。
**B+树查询效率更稳定。**B+树每次都必须查询到叶子节点才能找到数据，而B树查询的数据可能不在叶子节点，也可能在，这样就会造成查询的效率的不稳定
B+树的磁盘读写代价更小。B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，通常B+树矮更胖，高度小查询产生的I/O更少。

1、 B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2、B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

（2）聚集索引 VS 非聚集索引

那什么是聚集索引呢？在 MySQL 中，B+ 树索引按照存储方式的不同分为聚集索引和非聚集索引。

**聚集索引（聚簇索引）：**以 InnoDB 作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，系统也会帮你创建一个隐式的主键。

这是因为 InnoDB 是把数据存放在 B+ 树中的，而 B+ 树的键值就是主键，在 B+ 树的叶子节点中，存储了表中所有的数据。

这种以主键作为 B+ 树索引的键值而构建的 B+ 树索引，我们称之为聚集索引。
**非聚集索引（非聚簇索引）：**以主键以外的列值作为键值构建的 B+ 树索引，我们称之为非聚集索引。

非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。

明白了聚集索引和非聚集索引的定义，我们应该明白这样一句话：数据即索引，索引即数据。

（3）利用聚集索引和非聚集索引查找数据

如何通过聚集索引以及非聚集索引查找数据表中数据的方式介绍一下 B+ 树索引查找数据方法。

利用聚集索引查找数据

这就是聚类索引，表中的数据存储在其中。

举例：

现在假设我们要查找 id>=18 并且 id<40 的用户数据。对应的 sql 语句为：

select * from user where id>=18 and id <40

其中 id 为主键，具体的查找过程如下：

①一般根节点都是常驻内存的，也就是说页 1 已经在内存中了，此时不需要到磁盘中读取数据，直接从内存中读取即可。

从内存中读取到页 1，要查找这个 id>=18 and id <40 或者范围值，我们首先需要找到 id=18 的键值。

从页 1 中我们可以找到键值 18，此时我们需要根据指针 p2，定位到页 3。

②要从页 3 中查找数据，我们就需要拿着 p2 指针去磁盘中进行读取页 3。

从磁盘中读取页 3 后将页 3 放入内存中，然后进行查找，我们可以找到键值 18，然后再拿到页 3 中的指针 p1，定位到页 8。

③同样的页 8 页不在内存中，我们需要再去磁盘中将页 8 读取到内存中。

将页 8 读取到内存中后。因为页中的数据是链表进行连接的，而且键值是按照顺序存放的，此时可以根据二分查找法定位到键值 18。

此时因为已经到数据页了，此时我们已经找到一条满足条件的数据了，就是键值 18 对应的数据。

因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页 8 中的键值依次进行遍历查找并匹配满足条件的数据。

我们可以一直找到键值为 22 的数据，然后页 8 中就没有数据了，此时我们需要拿着页 8 中的 p 指针去读取页 9 中的数据。

④因为页 9 不在内存中，就又会加载页 9 到内存中，并通过和页 8 中一样的方式进行数据的查找，直到将页 12 加载到内存中，发现 41 大于 40，此时不满足条件。那么查找到此终止。

最终我们找到满足条件的所有数据，总共 12 条记录：

(18,kl), (19,kl), (22,hj), (24,io), (25,vg) , (29,jk), (31,jk) , (33,rt) , (34,ty) , (35,yu) , (37,rt) , (39,rt) 。

利用非聚集索引查找数据

在叶子节点中，不再存储所有的数据了，存储的是键值和主键。对于叶子节点中的 x-y，比如 1-1。左边的 1 表示的是索引的键值，右边的 1 表示的是主键值。

如果我们要找到幸运数字为 33 的用户信息，对应的 sql 语句为：

select * from user where luckNum=33

查找的流程跟聚集索引一样，我们最终会找到主键值 47，找到主键后我们需要再到聚集索引中查找具体对应的数据信息，此时又回到了聚集索引的查找流程。

下面看下具体的查找流程图：

在 MyISAM 中，聚集索引和非聚集索引的叶子节点都会存储数据的文件地址。

参考链接：刘召考的博客 » MySQL索引-B+树（看完你就明白了）

秒客网

数据库索引——B+树索引（为什么使用B+树作为MySql的索引结构，用什么好处？）