索引：为了提高数据查询的效率，就像书的目录一样。

索引的常见模型

哈希表

图中，User2 和 User4 根据身份证号算出来的值都是 N，后面还跟了一个链表。假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将 ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。

需要注意的是，图中四个 ID_card_n 的值并不是递增的，好处是增加新的 User 时速度会很快，只需要往后追加。缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。****

哈希表结构适用于只有等值查询的场景。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀。

要查 ID_card_n2 对应的名字，用二分法就可以快速得到，时间复杂度是 O(log(N))。同时很显然，这个索引结构也支持范围查询。

仅仅看查询效率，有序数组就是最好的数据结构。但是，在需要更新数据的时候就麻烦了，往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

所以，有序数组索引只适用于静态存储引擎。

N 叉树

二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。

如果你要查 ID_card_n2 的话，图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。时间复杂度是 O(log(N))。

为了维持 O(log(N)) 的查询复杂度，需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。

InnoDB 的索引模型

在 MySQL 中，索引是在存储引擎层实现的。

InnoDB 使用了 B+ 树索引模型，每一个索引在 InnoDB 里面对应一棵 B+ 树。

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

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

根据叶子节点的内容，索引类型分为主键索引和非主键索引。

• 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
• 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

基于主键索引和普通索引的查询区别？：

• select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
• select * from T where k=5，即普通索引查询方式，需要先搜索 k 索引树，得到 ID 值为 500，再到 ID 索引树搜索一次。这个过程称为回表。

基于非主键索引的查询需要多扫描一棵索引树，因此在应用中应该尽量使用主键查询。

索引维护

• 主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
• 有业务逻辑的字段做主键，则往往不容易保证有序插入，写数据成本相对较高。

从性能和存储空间方面考量，自增主键往往是更合理的选择。

同时适合用业务字段直接做主键的场景是：

• 只有一个索引；
• 该索引必须是唯一索引。

由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。

这时候优先考虑“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

问：对于 InnoDB 表 T，如果你要重建索引 k，你的两个 SQL 语句可以这么写：

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

如果你要重建主键索引，也可以这么写：

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

对于上面这两个重建索引的作法，说出你的理解。

答：为什么要重建索引。索引可能因为删除，或者页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，重建索引使得页面的利用率最高，也就是索引更紧凑、更省空间。

重建索引 k 的做法是合理的，可以达到省空间的目的。但是，重建主键的过程不合理。

不论是删除主键还是创建主键，都会将整个表重建。所以连着执行这两个语句的话，第一个语句就白做了。这两个语句，你可以用这个语句代替 ： alter table T engine=InnoDB。