MySQL 学习笔记 ----- 深入浅出索引（上）

索引

可以把索引理解为书的目录，比如书有 1000 页，想要找你想要看的部分，如果不用目录，那么查找起来就很费劲，用了目录之后，就能很方便的找到。所以索引就是为了方便查找数据，对于数据库的表而言，索引其实就是它的“目录”。

索引的常见模型

索引有三种常见的模型，分别是哈希表、有序数组、搜索树。
哈希表是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 Value。当出现哈希冲突时，一般采用的就是拉链法。注意这样的索引结构是无序的。

通过哈希函数计算要查询身份证号的哈希值，查到之后，按序查找相应链表中的值。对于单个查询这样很方便，如果是顺序区间查询，就需要全部扫喵一遍了，因为哈希表是无序的。

对于有序数组，，有序数组索引只适用于静态存储引擎，表里的信息是不会改动的，可以才用二分法。

搜索树

如果根据用二叉搜索树，来建立索引。

二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。这样以来，查找的时间复杂度 O(log(N))。为了维持这样的复杂度，需要保持这棵树是平衡二叉树，为了做这个保证，更新的时间复杂度也是 O(log(N))。

对于百万行的表来说，就是一个有 100 万行的节点二叉树，那么行高就是 ２０，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，访问速度太慢了。

所以我们不应该用二叉树，可以用 Ｎ 叉树。这样让查询过程访问尽量少的数据块，“N”取决于数据块的大小。

InnoDB 的索引模型

InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的,每一个索引在 InnoDB 里面对应一棵 B+ 树。

假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中 R1~R5 的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示例示意图如下。

B+ 树所有的关键字都出现在叶子节点的链表（稠密索引）中，且链表中的关键字是有序的。非叶子节点只起索引作用（稀疏索引）。

由图可以看出，根据叶子节点的内容，可分为主键索引和普通索引，主键索引的叶子节点的数据域存放的是该主键所在行的所有数据（聚簇索引），而普通索引子节点的数据域存放的主键（二级索引）。

如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树。
如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，ID 的值为 500，再到 ID 索引树搜索一次。这个过程称**回表**。
也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，**在应用中应该尽量使用主键查询。**

索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。如果数据页满了，按照 B+Tree 算法，新增加一个数据页，叫做页分裂，会导致性能下降。空间利用率降低大概 50%。

如果使用自增主键，每次插入操作都是在后面追加，不会导致叶子节点频繁移动，而触发页分裂。而且显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。**

重建索引

为什么要重建索引？
索引可能因为删除，或者页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。
对于上面例子中的 InnoDB 表 T，如果你要重建普通索引 k，你的两个 SQL 语句可以这么写：

alter table T drop index k;
alter table T add index(k);

这样做就是把索引这棵 B+ 树删掉，重建 k 索引，节省空间

对于重建主键索引，不能用下述 sql 语句做

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

因为不论是删除主键还是创建主键，都会将整个表重建。

声明：此篇文章的主体内容参考自极客时间的 MySQL 实战 45 讲，非本人原创，只是在学习的过程中觉得有必要将其写入个人博客之中，且最终目的只是为了方便自己或有需要的人进行查阅。此外，若需转载本文仍需本人同意。

上一篇：MySQL 学习笔记-----事务隔离