MySQL|索引背后

01

索引

以MySQL中的索引为例子总结。

数据库查询是数据库的最主要功能之一，实现高效的查询速度一定是MySQL非常关心的事情。

索引（Index）正是帮助MySQL高效获取数据的数据结构。

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，因此先看下这两种树的基本概念，至于B-Tree/B+Tree涉及的主要操作比如，裂变等，大家可以进一步参阅其他书籍或博客学习。

02

B-树

m阶B-树也称作（ceil(m), m）树，如(2,3)树，称为3阶B树，(2,4)树称为4阶B树。

如下为4阶B-树，每个节点至少含有2个分支，至多含有4个分支，也就是说，每个节点至少含有1个数据节点，至多含有3个数据节点。

03

B+树

B+树和m阶的B-树的差异在于：

1. 内节点(非叶子节点)，只用来索引；
2. 所有的外节点(叶子结点) 中包含了： 1) 全部关键字的信息 2) 指向含这些关键字记录的指针 3) 外节点(叶子结点) 本身依关键字的大小自小而大顺序链接。

如下所示，所有节点都有key域；叶节点的数据域上才真正存储着数据，而非叶节点的数据域只保存多个指针。

04

为什么是B+树?而不是红黑树

为什么MySQL选择了B+树，而不是红黑树作为数据库的索引呢？

B+Tree中一次检索最多需要h-1次I/O（根节点常驻内存），树的高度为O(logdN)。一般实际应用中，一个节点的分支数（出度d）是非常大的数字(通常大于100)，因此树的高度会非常小（通常不超过3）。索引设计为B+数据结构，一次检索所需要的I/O次数就会很小。我们又知道，访问内存的延迟大约为ns级，而访问磁盘的延迟为ms级，这相当于，访问内存延迟如果1天的话，访问外存延迟需要2000年。

根据磁盘预读原理，B+树将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里。

而红黑树这种结构，h明显要深的多。并且，红黑树中逻辑上很近的节点（父子）物理上可能很远，无法利用局部性。

综上，B+树更适合做索引。

05

MyISAM和InnoDB存储引擎

在MySQL中，不同存储引擎对索引的实现方式是不同的，总结下MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。

第一列作为主索引的MyISAM引擎存储结构，要求主索引取值唯一。

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM不同。InnoDB的叶子节点的数据域保存了完整的数据记录，索引的key是数据表的主键

06

InnoDB的主键选择与插入优化

在使用InnoDB存储引擎时，建议使用一个与业务无关的自增字段作为主键。

InnoDB将数据记录本身存于主索引（一颗B+Tree）的叶子节点上。每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。如下图所示：

这样就会形成一个紧凑的索引结构，近似顺序填满。

如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：

此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

因此，只要可以，请尽量在InnoDB上采用自增字段做主键。

知道了这些基本知识，如何加以运用呢？see you!

本文部分参考了关于介绍索引的文章：

http://blog.codinglabs.org/articles/theory-of-mysql-index.html

以上，如果疏漏错误，请指正。

希望时间的流逝不仅仅丰富了我们的阅历，更重要的是通过提炼让我们得以升华，走向卓越。