本篇文章博主对索引做了一个较为初步的概述，主要有2种主要的索引的数据结构b+tree和hash的数据结构，b+树的覆盖索引和回表进行分析，并对b+树存放记录、如何优化B+树索引的插入性能进行分析。

一、 MySQL索引数据结构模型

众所周知，数据库查询是数据库的核心功能，索引是加速查询的重要技术手段。

MySQL对索引的官方定义是存储引擎用来快速查找记录的数据结构。一般来说，索引类似于图书目录。它以增加写入和存储空间为代价，提高了数据库表上数据检索操作的速度。您可以根据其中记录的页码快速找到所需内容。

索引是物理数据页，数据库页面大小决定了页面可以存储多少索引行，以及存储指定大小的索引需要多少页面。索引数据结构选择的本质是根据当前数据读写的硬件环境，选择一个优秀的数据结构进行数据存储和遍历。

索引可以加快检索速度，但也可以降低插入、删除和更新索引列的速度。索引同时维护需要一定成本。

数据库中的大多数索引都是通过B+Tree实现的。当然，还涉及其他数据结构，索引涉及的理论知识包括哈希表和B+树。

1、B+Tree（B+树）索引

B+ 树索引是数据库中最常见的索引数据结构，为什么关系数据库热衷于支持B+树索引？

与二叉树、散列索引、红黑树和SkipList相比，在基于磁盘的海量数据存储效率方面远不如B+树索引，因此，上述数据结构通常仅用于内存对象。

对于基于磁盘的数据排序和存储，最有效的仍然是B+树索引。B+树索引的特点是基于磁盘的平衡树，树通常为3到4层，可以存储数千万到数亿的排序数据。树短意味着访问效率高。从数千万或数亿数据中查询一条数据只需要3或4个I/O。

因为SSD（固态硬盘）每秒可以执行至少10000个I/O，所以查询一段数据只需要0.003到0.004秒，即使数据都在磁盘上。此外，由于B+树较短，在排序时，它只需要比较3到4次，就能找到需要插入数据的位置。分拣效率非常好。

B+树索引由根节点、非叶节点和叶节点组成，其中叶节点存储所有排序的数据。

所有B+树都从高度为1开始，然后根据数据的插入慢慢增加树的高度。索引用于对记录进行排序，高度为1的B+树索引中存储的记录已排序，如果想在叶节点中进行查询，您可以只通过二进制搜索快速找到数据。

当一个页面（16K）无法存储如此多的数据，因此B+树将分裂。B+树的高度将变为2。当B+树高度大于或等于2时，根节点和中间节点存储由（索引键和指针）组成的索引键对。索引键是已排序的列，指针是指向下一层的地址，这在MySQL的InnoDB存储引擎中占用了6个字节。

2、Hash 索引

哈希表是数据库中哈希索引的基础。它是根据键值＜key，value＞存储数据的结构。

使用哈希函数计算桶或槽的索引列的数组。实际的存储是根据哈希函数将 key 转换为确定的存储位置，并将值存储在数组位置。访问时，只需要输入要搜索的 key ，然后就可以通过哈希函数计算确定的存储位置并读取数据。

在 MySQL 中主要是分为三种哈希索引：

Memory 存储引擎原生支持的 Hash 索引InnoDB 自适应哈希索引NDB 集群的哈希索引3、InnoDB 自适应哈希索引

InnoDB 自适应哈希索引旨在提高查询效率。

InnoDB 存储引擎将监视表上每个索引页的查询。当 InnoDB 注意到某些索引值被非常频繁地访问时，将基于B+树索引在内存中创建另一个哈希索引，从而使内存中的B+树具有哈希索引的功能，即可以快速访问具有固定值的频繁访问的索引页。

为什么要为B+树索引页创建自适应哈希索引？

这是因为B+树索引的查询效率取决于B+树的高度，在数据库中B+树的高度通常为3到4层，因此需要执行3到4个查询才能访问数据。

哈希索引可以在单个搜索中定位数据（没有哈希冲突），并且哈希索引在其等效查询场景中的查询效率优于B+树。

自适应散列索引的建立使 InnoDB 存储引擎能够根据索引页访问的频率自动为热点页创建散列索引，以加快访问速度。

二、B+ 树索引理论上每层最多能存放多少行记录

根节点最多可以存储键值对 = 16K/键值对大小（8+6）≈ 1100

叶节点存储的最大记录数 = 16K/每条记录的大小 ≈ 32

总记录数 = 根节点最多可以存储以下多个键值对 * 叶节点最多可以保存以下多个键值对

所以二层是1100*32 = 35200

树高为3的B+树索引中可以存储的最大记录数为：总记录数=1100（根节点）*1100（中间节点）*32 = 38720000

树高为4的B+树索引中可以存储的最大记录数为：总记录数=1100（根节点）*1100（中间节点）*1100（根节点）*32 = 42592000000

不过，在真实环境中，每个页利用率并没有这么高，还会存在一些碎片的情况，我们假设每个页的使用率为60%。十亿级别的数据量查询也只需要4次IO。

三、优化 B+ 树索引的插入性能

1、索引维护原理

为了维持索引的顺序，在插入、删除时需要维护B+树。

如果是插入，一般有三种情况：

1、只需要在页记录之后插入一条新记录。

2、需要按逻辑移动以下数据以腾出空间

3、需要申请一个新的数据页，然后将一些数据移到过去（分页）在这种情况下，性能自然会受到影响。

除性能外，页拆分还影响数据页的利用率。原来放在一个页上的数据现在被分成两个页，总体空间利用率降低了约50%。当然，有分裂的地方就有合并。

当由于删除数据而导致两个相邻页的使用率较低时，数据页将被合并。合并过程可视为拆分过程的反向过程。

2、每张表尽量使用自增ID主键

自增加主键的数据插入模式，每次插入新记录时，都是追加操作，它不涉及移动其他记录，也不触发叶节点的拆分，这样，可以避免最后两种影响性能的情况。

要确保以业务逻辑为主键的字段的有序插入并不容易，因此写入数据的成本相对较高。如果将业务逻辑的字段用作主键，通常不容易确保有序插入，因此写入数据的成本相对较高。

主键长度越小，索引的叶节点就越小，而索引占用的空间就越小。因此，从性能和存储空间的角度来看，自动增长的主键往往是一个更合理的选择。

四、B+树 覆盖索引与回表

回到主键索引树搜索过程，称为回表，查询结果所需的数据仅在主键索引上可用，必须将其返回到表中获取数据。

如果要执行的语句 select ID from T where，只需要查询ID值，并且ID值已经在k索引树上的话。可以直接提供查询结果而不返回表，这个查询,索引覆盖了我们的查询需求，我们称之为覆盖索引。

由于覆盖索引可以减少树搜索的数量并显著提高查询性能，因此使用覆盖索引是一种常见的性能优化方法。

如果现在有高频请求，可以在这个高频请求上使用覆盖率索引，无需返回表检查整行记录，并减少语句执行时间。当然，索引字段的维护总是有代价的。因此，在建立冗余索引以支持覆盖率索引时，有必要考虑权衡。

总结

本篇文章博主对索引做了一个较为初步地概述，主要有2种主要的索引的数据结构b+tree和hash的数据结构，b+树的覆盖索引和回表进行分析，并对b+树存放记录、如何优化B+树索引的插入性能进行分析。

作者：小明Java问道之路

链接：

来源：稀土掘金