索引是对数据库表中一列或多列的值进行排序的一种构造，应用索引可快速访问数据库表中的特定信息。能够将数据库索引和书的目录进行类比，通过书的目录咱们能够疾速查找到章节地位，如果没有目录就只能一页页翻书查找了。

索引数据结构

能够用于晋升查问效率的索引构造很多，常见的有 B 树索引、哈希索引和 B + 树索引。接下来咱们会对这些索引一一进行介绍，并阐明 InnoDB 为什么采纳 B + 树作为索引。

磁盘 IO

文件是存储在硬盘下面的。当下硬盘的读取速度非常无限，所以在进行查问定位某个数据的时候，应该尽可能地缩小磁盘 I / O 次数。

磁盘预读

因为存储介质的个性，磁盘自身存取就比主存慢很多，再加上机械运动消耗，磁盘的存取速度往往是主存的几百分之一，因而为了提高效率，要尽量减少磁盘 I /O。为了达到这个目标，磁盘往往不是严格按需读取，而是每次都会预读，即便只须要一个字节，磁盘也会从这个地位开始，程序向后读取肯定长度的数据放入内存。这样做的理论依据是计算机科学中驰名的局部性原理：当一个数据被用到时，其左近的数据也通常会马上被应用。程序运行期间所须要的数据通常比拟集中。

局部性原理：CPU 拜访存储器时，无论是存取指令还是存取数据，所拜访的存储单元都趋于汇集在一个较小的间断区域中。

预读的长度个别为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区宰割为间断的大小相等的块，每个存储块称为一页（在许多操作系统中，页的大小通常为 4k），主存和磁盘以页为单位替换数据。当程序要读取的数据不在主存中时，会触发一个缺页异样，此时零碎会向磁盘收回读盘信号，磁盘会找到数据的起始地位并向后间断读取一页或几页载入内存中，而后异样返回，程序持续运行。

正当利用磁盘预读

一般来说，索引自身也很大，不可能全副存储在内存中，因而索引往往以索引文件的模式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I / O 耗费，绝对于内存存取，I/ O 存取的耗费要高几个数量级，所以评估一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I / O 操作次数。换句话说，索引的构造组织要尽量减少查找过程中磁盘 I / O 的存取次数。

如果咱们能正当应用磁盘预读的个性，使每次磁盘 IO 读到的页中的数据都是有用的，就能够大大晋升数据的查问效率。

B 树索引

B 树能够看作是对二叉查找树的一种扩大，B 树容许每个节点有 M - 1 个子节点，B 树有以下特点：

1. 根节点至多有两个子节点；
2. 每个节点蕴含 M - 1 条数据，节点中的数据装置索引递增程序排序；
3. 节点中有最多有 M 个指针指向下一层节点，这些指针位于节点的多个数据之间，下一层节点的所有数据值大于指针左侧的数据，小于指针右侧的数据；
4. 每个节点至多蕴含 M / 2 条数据；

接下来咱们用下示意例的用户数据来构建 B 树，如表所示，用户数据蕴含姓名、性别、年龄三个字段，咱们把用户年龄作为数据库主键(假如年龄具备唯一性)，那么构建进去的 B 树的构造如下图所示。

![B 树索引]

相比拟与常见的二叉树，B 树的一个节点中寄存了更多的数据，这样做能够无效的缩小一次数据查找过程中的磁盘 IO 次数：

• 二叉树每个节点只寄存一个数据，节点之间用指针关联，节点之间的空间是离散的，所以每个节点都对应一次磁盘 IO，查找一次数据的 IO 次数为 O($log_2$N)；
• B 树的节点能够寄存 M - 1 个数据，如果这 M - 1 个数据刚好能够放到一个页中，那么 B 树查找一次数据的 IO 次数为 O($log_M$N)；

哈希索引

哈希索引基于哈希表实现，只有准确匹配索引所有列的查问才无效。哈希表是一种以键 - 值 (Key-Value) 存储数据的构造，用户能够在 O(1)工夫复杂度内依照 Key 查找到对应的 Value。

哈希表通常是一个数组，数据在数组中的地位能够依照索引的值装置哈希算法进行计算，如果两个数据的索引值计算出来的地位雷同，那么通常能够采纳链地址法解决抵触（其它解决地址抵触的办法还有凋谢定制法，链地址法，公共溢出区法，再散列法等）。

如下表数据所示，咱们仍旧依照用户的年龄为用户数据建设索引(假如用户年龄不会雷同)，咱们采纳的哈希算法为 addr=age%10，咱们能够建设长度为 10 的数组作为哈希表，依照哈希函数一一把用户放入哈希表，依照用户年龄查找用户时，能够间接计算出用户所在的地位，从而失去用户信息，最终失去的哈希表以及查问流程如下图所示。

哈希索引有以下长处：

1. 占用的额定空间小，为数据新建一个哈希索引须要的额定空间为 O(N)，和索引字段长度无关；
2. 查问速度极快，哈希函数正当的状况下，程序能够在 O(1)的磁盘 IO 次数内查找到数据；

哈希索引有以下毛病：

1. 无奈进行范畴查问，哈希过程中曾经失落了索引的程序性；
2. 无奈对数据进行排序查找，比方查找年龄最大的用户；
3. 无奈应用局部索引查找，比方前缀查问等；
4. 哈希函数不合理的状况下，会导致哈希抵触问题，造成查问效率变低；

B+ 树索引

InnoDB 应用的索引的数据结构是 B + 树，数据库表定义中的每一个索引对应一颗 B + 树，默认的聚簇索引也是一颗 B + 树，B+ 树有以下特色：

1. 所有节点关键字是按递增秩序排列，并遵循左小右大准则；
2. 非叶节点的子节点数在 1 到 M 之间(下图中 M 为 3)，空树除外；
3. 非叶节点的索引数目大于等于 ceil(M/2)个且小于等于 M 个；
4. 所有叶子节点均在同一层，叶子节点之间有从左到右的指针；
5. 数据存储在叶子节点，非叶子节点只存储索引；

接下来咱们用几条示例的用户数据来构建 B + 树，如表所示，用户数据蕴含姓名、性别、年龄三个字段，咱们把用户年龄作为数据库主键(假如年龄具备唯一性)，那么构建进去的 B + 树的构造如下图所示。

B+ 树索引数据结构有以下列出的几种劣势：

1. 查问性能稳固，查问一条数据须要的 IO 次数往往是树的高度次；
2. 范畴查问效率高，装置索引范畴查问时，能够先查找的第一个满足要求的数据，而后向后遍历，直到第一个不满足条件的数据为止，两头的数据都符合要求；
3. 查问效率高，往往一次数据查问只须要 2~3 次磁盘 IO；
4. 叶子节点存储所有数据，不须要去 B + 树之外找数据；

InnoDB 为什么采纳 B + 树

在 InnoDB 引擎中，咱们为数据库创立的索引都是以 B + 树的模式存在，为什么 InnoDB 不采纳哈希索引或者 B 树索引呢？次要是基于以下起因：

• 数据库查问常常会呈现非等值查问，哈希索引在这种状况下无奈工作；
• 相比于 B 树，B+ 树索引非叶子节点不存放数据，从而磁盘一次 IO 能够读取更多的索引数据，无效缩小磁盘 IO 次数；
• 数据库查问常常会呈现范畴查问，B+ 树底层的叶子节点之间依照顺序排列，能够更无效的实现范畴查问；

自增主键

通过上文咱们晓得，B+ 树须要保护索引的有序性。

1. 当用户向 B + 树插入数据，如果插入点对应的节点有空余地位，那么只须要移动节点中的数据，并把须要插入的数据放入 B + 树即可；
2. 当用户向 B + 树插入数据，如果插入点对应的节点没有空余地位，那么就须要生成一个新的节点，并把一部分数据挪过来；这种状况不仅会影响插入效率，因为决裂进去的节点只有局部数据，所以会导致空间的利用率升高；
3. 当用户删除 B + 树中的数据时，如果节点或相邻节点的数据量很少，那么只须要间接删除数据，并按移动节点中的其它数据即可；
4. 当用户删除 B + 树中的数据时，如果节点和相邻节点的数据量很少，那么在删除之后，可能须要把节点和相邻节点合并，从而进步空间利用率；

基于 B + 树须要保护索引有序性的特点，咱们对索引字段提出以下倡议：

1. 对于数据插入比拟多的场景，主键索引字段最好是递增的。递增的主键每次插入一条新记录，都是追加操作，都不波及到移动其余记录，也不会触发叶子节点的决裂。
2. 主键索引的长度该当尽量小，主键长度越小，一般索引的叶子节点就越小，一般索引占用的空间也就越小。

在 InnoDB 中，咱们该当尽量应用自增主键，自增主键有插入效率高、占用空间小等劣势。

数据空洞与重建索引

数据空洞

当你对 InnoDB 进行批改操作时，例如删除一些行，这些行只是被标记为“已删除”，而不是真的从索引中物理删除了，因此空间也没有真的被开释回收。InnoDB 的 Purge 线程会异步的来清理这些没用的索引键和行，然而仍然没有把这些释放出来的空间还给操作系统从新应用，因此会导致页面中存在很多空洞。如果表构造中蕴含动静长度字段，那么这些空洞甚至可能不能被 InnoDB 从新用来存新的行，因为空间空间长度有余。

数据空洞带来的问题：

1. 删除表中的数据后，表占用的空间不会变小，造成空间节约；
2. 会升高数据查问的速度，因为空洞会占用页空间；

咱们能够通过以下 SQL 来查看数据库中的空洞大小，执行语句如下所示，返回后果中的 DATA_FREE 示意表中闲暇数据块的大小。

select data_length,data_free from information_schema.tables where table_schema='test' and table_name='test';

重建索引

当一张表的索引中的数据空洞过多时，会影响 SQL 语句的执行效率，此时咱们就须要清理这些数据空洞。

清理数据空洞比拟好的方法是重建索引，因为重建索引的过程中，会依照索引的大小排序后建设索引，建设进去的索引比拟紧凑。

有什么方法能够重建索引呢？咱们比拟直观的想法必定是先删除索引，再重建索引。然而不论是删除主键还是创立主键，都会将整个表重建。所以连着执行这两个语句的话，第一个语句就白做了。

alter table user_info drop primary key;
alter table user_info add primary key(id);

InnoDB 中能够通过以下转换数据引擎的语句来重建表的所有索引。这是因为在转换数据引擎（即便没有真正转换）的过程中，会读取表中所有的数据，再从新写入，这个过程中，会开释空洞。须要留神的是，通过这种办法重建索引耗时比拟长。

alter table test engine=innodb

本文最先公布至微信公众号，版权所有，禁止转载！