索引的常见模型
实现索引的方式有很多种。可用于提高读写效率的数据结构很多。这里有三种常见也比较简单的数据结构，哈希表、有序数组和搜索树。
哈希表是一种以键 - 值（key-value）存储数据的结构。哈希的思路很简单，把值放在数组中，用一个哈希函数把 key 换算成一个确定的位置，然后把数据存放在对应位置。
当多个 key 值经过哈希函数计算，出现同一个值时。处理这种情况的方法就是拉出一个 链表。
图中，User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将 ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。
需要注意的是，图中四个 ID_card_n 的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。
你可以设想下，如果你现在要找身份证号在[ID_card_X, ID_card_Y]这个区间的所有用户，就必须全部扫描一遍了。
所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。
而有序数组在等值查询和范围查询场景中的性能就都非常优秀。
在有序数组中，查询数据时用二分法就可以快速得到，查询的时间复杂度是 O(log(N))。
但是在插入数据的时候，必须挪动后边所有的记录，成本很高，所以，有序数组索引只适用于静态存储引擎。比如是一些不会再修改的数据。
二叉搜索树也是课本里经典的数据结构了。
二叉搜索树的特点是，左儿子节点小于父节点，父节点又小于右儿子。查询的时间复杂度是O(log(N))。
为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。
在实际应用中，大多数的数据库存储并不使用二叉树，因为索引不只存在内存中，还要写在磁盘里。如果是一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。
为了减少查询时读磁盘的次数，就必须让查询过程访问尽量少的数据块。所以不应该使用二叉树，而是使用“N叉”树。
InnoDB 的一个整数字段索引中的这个“N”差不多是1200。当树高是4的时候，就可以存储 1200 的三次方的值，已经高达17亿了。
N叉树在读写上的性能有点，以及适配磁盘的访问模式，已经在数据库中被广泛应用了。
索引是在引擎层实现，不同的存储引擎的索引工作方式也不一样。
InnoDB 索引模型
在 InnoDB中，表都是根据主键顺序以索引的形式存放的。这种存储方式的表称之为索引组织表。InnoDB 使用了B+ 树的索引模型，所以数据都在存储在 B+ 树中的。
每一个索引在InnoDB 中都对应一棵 B+ 树。
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
假设一张表有主键索引和一般索引，那么在Innodb 中，就有两棵索引树。
主键索引的叶子节点存储的是整行数据，在 InnoDB 中，主键索引也被称之为 聚簇索引（clustered index）。
非主键索引的叶子节点的内容是主键的值。在InnoDB 中，非主键索引也被称为二级索引（secondary inde）。
基于主键索引和普通索引的查询有什么区别？
如果使用主键查询方式，则只需要搜索 ID 这棵树；
如果使用的是索引查询方式，则需要先搜索 k 索引树，得到 k 值对应的 ID 的值，再回到 ID 这棵树搜索一次，这个过程称之为回表。
索引维护
为了维护索引的有序性，在插入新值的时候就需要做必要的维护。如上图所示，如果插入了一个 ID 为400 的值，则必须把 R4 之后的数组挪动，空出位置。
而在挪动的时候，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，就需要申请一个新的数据页，然后挪动部分数据过去，这个过程称为页分裂。在这种情况下，除了性能会受到影响，数据的页利用率也会降低。
所以在一些建表规范中，要求建表一定要有自增主键。自增主键的数据模式，正好符合了递增插入的场景。每次插入一条新纪录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
除了考虑性能外，我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？
由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。
显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
如果表中只有一个索引，而且该索引一定是唯一索引，就要优先考虑 “尽量使用主键查询” 原则，直接将这个索引设置成主键，可以避免每次查询都需要搜索到两棵树。
小结
InnoDB 采用 B+ 树的结构，这种结构能够很好地配合磁盘的读写特性，减少单次查询的磁盘访问次数。
由于InnoDB 是索引组织表，一般情况下都建议创建一个自增主键，这样非主键索引占用的空间最小。
回表
如果一个表中有一个主键索引，有一个普通索引，当使用普通索引查询数据时，会先到普通索引树上查找数据，然后根据查找到的主键的值，回到主键索引树上搜索，这个回到主键索引树搜索的过程，我们称之为回表。
覆盖索引
如果在查询的过程中只查询主键，或者说只查询索引树上已有的内容，就可以减少回表，显著提升查询性能。也就是说，在查询里，索引已经“覆盖”了我们的查询需求，我们称之为覆盖索引。
如果一个表有高频请求，同时查询两个字段，那么这个联合索引就有意义了。
最左前缀原则
B+ 树的这种索引结构，是可以利用索引的 “最左前缀”，来定位记录的。
最左前缀原则可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。
如果调整顺序，可以少维护一个索引，那么应该优先考虑这种顺序。
索引下推
我们还是以市民表的联合索引（name, age）为例。如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。那么，SQL 语句是这么写的：
mysql> select * from tuser where name like '张%' and age=10 and ismale=1;
在MySQL 5.6 之前，这个语句在搜索索引树时，只能使用“张”，找到第一个满足记录的id，然后回表，再比较其他字段。
在 MySQL 5.6 之后引入了索引的下推优化（index coondition pushdown），可以再索引遍历的过程中，对索引中包含的字段做判断，直接过滤掉不满足条件的记录，减少回表次数。
小结
在满足语句要求的情况下，尽量少地访问资源是数据库设计的重要原则之一。我们在使用数据库的时候，尤其是在设计表结构时，也要以减少资源消耗作为目标。
