共计 3195 个字符，预计需要花费 8 分钟才能阅读完成。
索引简介
索引是一种数据结构，索引的呈现是为了进步数据查问的效率。查问效率个别能够从等值查问和范畴查问两个方面进行评判。
索引的模型
哈希表
哈希表是一种以键 – 值（key-value）存储数据的构造，哈希的思路很简略，把值放在数组里，用一个哈希函数把 key 换算成一个确定的地位，而后把 value 放在数组的这个地位。
不同的 key 值通过哈希函数的换算，会呈现同一个值的状况。解决这种状况的一种办法是，拉出一个链表。
假如，当初保护着一个身份证信息和姓名的表，须要依据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：
哈希表因为能够疾速的找到数据的地位，等值查问效率十分高，但哈希表中的值因为不保障程序，如果要查问某个范畴内的数据，就须要把整个哈希表中的值进行扫描判断。所以哈希表这种数据结构适宜比拟适宜等值查问，不适宜范畴查问的场景。
有序数组
有序数组保障了数组中的元素的值是依照肯定顺序存储的，还是下面的例子，假如身份证是不反复的，如下图：
如果要查 ID_card_n2 对应的名字，用 二分法 就能够疾速失去，这个工夫复杂度是 O(log(N))。
同时，这个索引构造反对范畴查问。要查身份证号 [ID_card_X, ID_card_Y] 区间的 User，能够先用 二分法 找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），而后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。
如果仅仅看查问效率，有序数组就是比拟好的数据结构了。然而，在须要更新数据的时候就比拟麻烦了，往两头插入一个记录就必须得移动前面所有的记录，老本太高。所以，有序数组索引只实用于动态存储引擎。
二叉树
还是下面依据身份证号查名字的例子，如果咱们用二叉搜寻树来实现的话，示意图如下所示：
二叉搜寻树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。这样如果要查 ID_card_n2 的话，依照图中的搜寻程序就是依照 UserA -> UserC -> UserF -> User2 这个门路失去。这个工夫复杂度是 O(log(N))。
当然为了维持 O(log(N)) 的查问复杂度，你就须要放弃这棵树是均衡二叉树。为了做这个保障，更新的工夫复杂度也是 O(log(N))。
树能够有二叉，也能够有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保障从左到右递增，如图：
二叉树是搜寻效率最高的，然而实际上大多数的数据库存储却并不应用二叉树。其起因是，索引不止存在内存中，还要写到磁盘上。
如果数据库存储应用二叉树，那么树的高度就比拟大，设想一下一棵 100 万节点的均衡二叉树，树高 20。一次查问可能须要拜访 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块须要 10 ms 左右的寻址工夫。也就是说，对于一个 100 万行的表，如果应用二叉树来存储，独自拜访一个行可能须要 20 个 10 ms 的工夫。
为了让一个查问尽量少地读磁盘，就必须让查问过程拜访尽量少的数据块。那么，就不应该应用二叉树，而是要应用“N 叉”树来实现缩小树的高度。这里，“N 叉”树中的“N”取决于数据块的大小。
对于雷同个数的数据构建 N 叉树索引，N 叉树中的 N 越大，那树的高度就越小，那 N 叉树中的 N 是不是越大越好呢？到底多大才最合适呢？
不论是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值能够通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发屡次 IO 操作。所以，咱们在抉择 N 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只须要一次磁盘 IO 操作。
N 叉树因为在读写上的性能长处，以及适配磁盘的拜访模式，曾经被广泛应用在数据库引擎中了。
InnoDB 的索引
索引模型
InnoDB 应用了 B+ 树索引模型，数据都是存储在 B+ 树中。每一个索引在 InnoDB 外面对应一棵 B+ 树。在 B + 树中，叶子节点通过一个有序的双向链表串起来。
假如，咱们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引，表中 R1~R5 的 (ID,k) 值别离为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵 B+ 树的示例示意图如下：
依据叶子节点的内容，索引类型分为主键索引和非主键索引：
1、主键索引的叶子节点存储的是 Page，Page 中是一个有序数组，通过二分法定位到对应的数据行。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
2、非主键索引的叶子节点内容是 主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
主键索引和一般索引查问的区别：
如果语句是 select * from T where ID=500，即主键查问形式，则只须要搜寻 ID 这棵 B+ 树；
如果语句是 select * from T where k=5，即一般索引查问形式，则须要先搜寻 k 索引树，失去 ID 的值为 500，再到 ID 索引树搜寻一次。这个过程称为回表。
所以，基于非主键索引的查问须要多扫描一棵索引树。因而，在利用中应该尽量应用主键查问。
索引的类型
Normal：示意一般索引
Unique：示意惟一的，不容许反复的索引，如果该字段信息保障不会反复例如身份证号用作索引时，可设置为 unique
Full Text: 示意全文搜寻的索引。FULLTEXT 用于搜寻很长一篇文章的时候，成果比拟好
索引的保护
B+ 树为了保护索引有序性，在插入新值的时候须要做必要的保护。以下面这个图为例，如果插入新的行 ID 值为 700，则只须要在 R5 的记录前面插入一个新记录。
如果新插入的 ID 值为 400，就绝对麻烦了，须要逻辑上移动前面的数据，空出地位。而更糟的状况是，如果 R5 所在的数据页 P1 曾经满了，依据 B+ 树的算法，这时候须要申请一个新的数据 Pn，而后 P1 上须要移动局部数据到 Pn。本来在 P1 上的数据当初散布在 P1 和 Pn 两个数据页上了，这个过程称为页决裂。在这种状况下，性能天然会受影响。
除了性能外，页决裂操作还影响数据页的利用率。本来放在一个页的数据，当初分到两个页中，整体空间利用率升高大概 50%。
有决裂就有合并。当相邻两个页因为删除了数据，利用率很低之后，会将数据页做合并。合并的过程，能够认为是决裂过程的逆过程
自增主键
自增主键的插入数据模式，正合乎了咱们后面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不波及到移动其余记录，也不会触发叶子节点的决裂。而有业务逻辑的字段做主键，则往往不容易保障有序插入，这样写数据老本绝对较高。
除了思考性能外，咱们还能够从存储空间的角度来看。假如你的表中的确有一个惟一字段，比方字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？
因为每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只有 4 个字节，如果是长整型（bigint）则是 8 个字节。
显然，主键长度越小，一般索引的叶子节点就越小，一般索引占用的空间也就越小。所以，从性能和存储空间方面考量，自增主键往往是更正当的抉择。
索引的重建
索引可能因为删除，或者页决裂等起因，导致数据页有空洞，重建索引的过程会创立一个新的索引，把数据按程序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。
在非聚簇索引上应用索引重建，能够达到省空间的目标。比方：
alter table T drop index k;
alter table T add index(k);然而，重建主键索引的过程须要留神。不论是删除主键还是创立主键，都会将整个表重建。所以其余保护好的索引就白保护了。主键索引的重建，能够用这个语句代替：
alter table T engine=InnoDB;
