一文理解 InnoDB 为什么常用 B+ 树做索引

作者 |  宋光璠

责编 | 刘静

出品 | CSDN博客

B+树索引介绍

什么是索引

InnoDB 存储引擎的最小储存单元是页（Page），一个页的大小是 16K。 InnoDB存储引擎的所有数据文件（后缀为 .ibd 的文件），它的大小始终都是 16K的整数倍。 页的大小一般也是可以设置的，如下命令可以查看当前页的大小。

数据表中的数据存储在页中，假设一行数据的大小是 1K，那么一个页可以存放 16 行这样的数据。如果数据库只按这样的方式存储，那么查找数据将是一个问题，因为我们不知道数据存储在哪个页中，也不可能所有的页都遍历一遍。那样做就太慢了。为了解决这个问题，数据库系统维护了一种特殊的能够满足某种高级查找算法的数据结构，这个数据结构以某种方式指向具体的数据。我们把这个数据结构称为索引。

索引的作用

创建索引可以加快数据的检索速度，大大提高数据库系统的性能。 它会影响where后面的查找，和order by后面的排序，可以显著减少排序的时间。 但是不能为表的每个字段创建索引，因为增加索引也有些问题。 比如索引本身就需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。 当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

索引的分类

从存储结构上：

B类索引（B-树或者B+树索引），哈希索引、全文索引（full-text index）, R树索引

从应用上来分：

普通索引、唯一索引、复合索引

数据的物理顺序与键值的顺序关系：

聚簇索引、非聚集索引

在InnoDB存储引擎支持三种常用索引

• 哈希索引

• 全文索引

• B+树索引

InnoDB会根据表的情况自动生成哈希索引，不能人为干预表生成哈希索引

全文索引是将存在数据库的整本书的任意内容信息查找出来的技术，InnoDB从1.2.x版本支持。每张表只能有一个全文检索的索引。

B+树索引是传统意义上的索引，关系型数据库系统中查找最为常用也是最为高效的索引。 它的构造类似于二叉树，根据键值对（key, value）查找数据。 其中的B不是Binary，而是Balance的意思。 它的本质就是B+树在数据库中的实现。 它有一个特点就是高扇出性，因此在数据库中，B+树的高度一般是2-4层，也就是说查找某一键值对应的行记录只需要2-4次IO。

B+树是为了磁盘及其他存储辅助设备而设计的一种平衡查找树，在B+树中，所有记录的节点按大小顺序存放在同一层的叶节点中，各叶子节点用指针进行连接。 还是来个例子有个直观感受吧，下图的B+树，高度为2，每页存放4条行记录，扇出是5。

哈希索引的数据组织方式

哈希索引（Hash Index）基于哈希表实现，只有精确的匹配索引所有列的查询才有效。 对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。 哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

对于hash相同的，采用链式的方式解决。 这一点同hashmap比较相似。

举个例子， 假设有一张customer表，有id、name、age三个字段，表结构如下图所示：

create table customer(

id bigint NOT NULL,

name varchar(30) NOT NULL,

age int(11) NOT NULL, KEY USING HASH(name),PRIMARY KEY(id))engine=innodb;

表结构如下：

假设现在执行select age from customer where name=‘song’,则是先计算‘song’的哈希值，并使用该值对应的记录指针，比如f(‘song’)=2734,所以mysql在索引中查找2734，可以找到对应第1行的指针，最后再比较第1行的值是否为’song’。

所以通过分析，Hash 索引也有它的缺点

因为Hash索引比较的是经过Hash计算的值，所以只能进行等式比较，不能用于范围查询

由于哈希值是按照顺序排列的，但是哈希值映射的真正数据在哈希表中就不一定按照顺序排列，所以无法利用Hash索引来加速任何排序操作

不能用部分索引键来搜索，因为组合索引在计算哈希值的时候是一起计算的。

当哈希值大量重复且数据量非常大时，其检索效率并没有Btree索引高的。

B+树的数据组织方式

B+树索引分为聚集索引(cluster index)和辅助索引(secondary index)，聚集索引按表的主键构造的B+树，叶子节点存放整张表的行记录数据，每张表只能有一个聚集索引。 一般优化器更倾向采用聚集索引，因为直接就能获取行数据。 下面我们以一个聚集索引的例子来理解B+树的数据组织方式。

根绝customer表，那么B+树的数据方式组织如下图所示：

现将数据记录按主键进行排序，分别存放在不同页中（这里假设一个页只存放3条记录），可以看到，除了数据页以外还有存放键值和指针的页，比如图中page number=3的页，该页存放键值和指向数据页的指针。 这样的数据组织形式，一般称为索引组织表。

那么，假设现在要查找一条数据，该怎么查，比如：

select * from where id=4;

在这里选择自增id来做主键，通过这课B+树来查找，首先查找根页。 一般来说，每个表的根页位置在表空间中都是不变的，在这里也就是page number=3的页。 找到根页后通过二分查找法，定位到id=4的页应该在指针P5指向的页中。 将该页读入内存后，继续去page number=5的页中查找，即可查找到id=4的对应记录了。

所以InnoDB中，B+树组织及查询数据总结起来，主要有以下两点:

页可以用来存放记录，也可以用来存放键值+指针，所有记录的节点按照大小顺序存放在同一层叶子节点中，非叶子节点用来存放键值+指针，键值一般是页面中的最小值(Low Key);

索引组织表只能通过非叶子节点的二分查找法以及指针确定数据在哪个页中，然后通过把查找到的页读入内存后，再在内存中进行查找记录行。

为什么B+树比B树更适合做索引

B树也是多叉树结构，一种自平衡的树，而且B+树是从B树演化而来的，那么为什么不使用B+树的前身B树呢？ 从结构比较来看，B树相比B+树的一个主要区别就在于B树的分支节点上存储着数据，而B+树的分支节点只是叶子节点的索引而已。 根据这个差别可以得出以下结论：

磁盘IO读写次数相比B树降低了

在B+树中，其非叶子的内部节点都变成了key值，因此其内部节点相对B 树更小。 如果把所有同一内部节点的key存放在同一盘块中，那么盘块所能容纳的key数量也越多。 一次性读内存中的需要查找的key值也就越多。 相对来说IO读写次数也就降低了。

每次查询的时间复杂度是固定的

在B+树中，由于分支节点只是叶子节点的索引，所以对于任意关键字的查找都必须从根节点走到分支节点，所有关键字查询路径长度相同，每次查询的时间复杂度是固定的。 但是在B树中，其分支节点上也保存有数据，对于每一个数据的查询所走的路径长度是不一样的，所以查询效率也不一样。

遍历效率更高

由于B+树的数据都存储在叶子节点上，分支节点均为索引，方便扫库，只需扫一遍叶子即可。 但是B树在分支节点上都保存着数据，要找到具体的顺序数据，需要执行一次中序遍历来查找。 所以B+树更加适合范围查询的情况，在解决磁盘IO性能的同时解决了B树元素遍历效率低下的问题。

B+树作为索引可以存放多少数据

有道面试题，问InnoDB中，一颗的B+树可以存放多少行数据？

那么我们该如何计算呢？ 假设我们定义一颗B+树高度为2，即一个根节点和若干叶子节点。 那么这课B+树的存放总行记录数=根节点指针数*单个叶子记录的行数。 这里先计算叶子节点，B+树中的单个叶子节点的大小为16K，假设每一条目为1K，那么记录数即为16(16k/1K=16)，然后计算非叶子节点能够存放多少个指针，假设主键ID为bigint类型，那么长度为8字节，而指针大小在InnoDB中是设置为6个字节，这样加起来一共是14个字节。 那么通过页大小/(主键ID大小+指针大小），即16384/14=1170个指针，所以一颗高度为2的B+树能存放18720条这样的记录。 根据这个原理就可以算出一颗高度为3的B+树可以存放1170*1170*16=21902400条记录。 所以在InnoDB中B+树高度一般为2-3层，它就能满足千万级的数据存储。

原文链接：

https://blog.csdn.net/songguangfan/article/details/102475002

版权声明：本文为 CSDN 博主「 .NY&XX 」的原创文章。

扫描下方二维码，查看博主精彩分享！

 热 文 推 荐 

☞ 20 行 Python 代码说清量子霸权！

☞ 为何Google、微软、华为将亿级源代码放一个仓库？

☞ 为什么我会重回到Windows的怀抱？

☞上海梦醒互联网

☞漫画：要跳槽？这道缓存设计题你有必要看看！

☞ 深度学习可解释性问题如何解决？ 图灵奖得主Bengio有一个解

 ☞人民网：“三种眼光”读懂区块链的今天和明天

点击阅读原文，精彩继续。

你点的每个“在看”，我都认真当成了喜欢