二叉搜索平衡树
为了保证插入效率，使用了平衡树，平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
还是上面根据身份证号查名字的例子，如果我们用二叉搜索树来实现的话，示意图如下所示
这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))，当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))
多叉搜索树
树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上，因为二叉树树高过高，每次查询都需要访问过多节点，即访问数据块过多，而从磁盘随机读取数据块过于耗时
为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块，那么，我们就不应该使用二叉树，而是要使用N叉树。
以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了
InnoDB索引模型
在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的，每一个索引在 InnoDB 里面对应一棵 B+ 树
B+树结构
一个m阶的B+树具有如下几个特征：
- 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
- 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素
下图为一个B+树的结构：
在等值查询的时候：
区间查询：
B+树的优势显而易见：
- 单一节点存储更多的元素，使得查询的IO次数更少。
- 所有查询都要查找到叶子节点，查询性能稳定。
- 所有叶子节点形成有序链表，便于范围查询。
需要注意数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针，这部分再下文中讲到
B+Tree适用场景
我们这里比较下Hash索引和B+树的区别，有序数组暂不讨论。由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。 Hash 索引不能够用于诸如 < 等用于查找一个范围值的比较运算符，Hash 索引仅仅能满足”=”,”IN”和”<=>”（等价于）查询
- Hash 索引不能够用于范围查询，B+Tree可以进行范围查询
- Hash 索引无法被用来数据的排序操作，B+Tree可以进行排序操作，由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；优化器不能够使用 hash 索引来加速 ORDER BY 操作。这种类型的索引不能够用于按照顺序查找下一个条目。
- Hash 索引不能利用部分索引键查询。B+Tree可以，对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。查找某行记录必须进行全键匹配。而 B+Tree 索引，任何该键的左前缀都可用以查找记录。
- Hash 索引在任何时候都不能避免表扫描。前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
- Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B+Tree索引高，对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。
总而言之，还是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)，两棵树的示例示意图如下
可以看到表里创建了两个索引，一个是默认给主键创建的，一个是我们手动给k创建的：
- 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）
- 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引(非聚簇索引)（secondary index）
主键索引： key:主键的值，value:整行数据。 普通列索引： key：索引列的值， value:主键的值。
根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？
- 如果语句是
select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树； - 如果语句是
select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。
也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询
索引维护
B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。以上图为例
- 如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。
- 如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据空出位置。
以上情况维护起来就比较麻烦了。
页分裂和页合并
而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。页合并的过程，可以认为是分裂过程的逆过程
自增主键
自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。插入新记录的时候可以不指定 ID 的值，系统会获取当前 ID 最大值加 1 作为下一条记录的 ID 值
- 自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
- 业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高
除了考虑性能外，我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。所以，从性能和存储空间方面考量，自增主键往往是更合理的选择
业务主键
有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：只有一个索引；该索引必须是唯一索引。这就是典型的 KV 场景。由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树
MyISAM和InnoDB的索引实现对比
上文我们了解了InnoDB的索引结构。MySQL的BTree索引使⽤的是B树中的B+Tree，但对于主要的两种存储引擎的实现⽅式是不同的。
- MyISAM: B+Tree叶节点的data域存放的是数据记录的地址。在索引检索的时候，⾸先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。⾮聚簇索引
- InnoDB: 其数据⽂件本身就是索引⽂件。相⽐MyISAM，索引⽂件和数据⽂件是分离的，其表数据⽂件本身就是按B+Tree组织的⼀个索引结构，树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据⽂件本身就是主索引。聚簇索引。⽽其余的索引都作为辅助索引，辅助索引的data域存储相应记录主键的值⽽不是地址，这也是MyISAM不同的地⽅。在根据主索引搜索时，直接找到key所在的节点即可取出数据；在根据辅助索引查找时，则需要先取出主键的值，再⾛⼀遍主索引。
在设计表的时候，不建议使⽤过⻓的字段作为主键，也不建议使⽤⾮单调的字段作为主键，这样会造成主索引频繁分裂
索引策略
理解了InnoDB索引实现的方式之后，我们再来看看索引在具体的使用过程中有哪些执行策略和优化方式。
我们来看下select * from T where k between 3 and 5SQL 查询语句的执行流程，注意取3和取5因为叶子节点单链表链接，所以从根节点搜索行为仅执行一次。
- 在 k 索引树上找到 k=3 的记录，取得 ID = 300；再到 ID 索引树查到 ID=300 对应的 R3；回表
- 在 k 索引树取下一个值 k=5，取得 ID=500；再回到 ID 索引树查到 ID=500 对应的 R4；回表
- 在 k 索引树取下一个值 k=6，不满足条件，循环结束。
在这个过程中，回到主键索引树搜索的过程，我们称为回表。可以看到，这个查询过程读了 k 索引树的 3 条记录，回表了两次。在这个例子中，由于查询结果所需要的数据只在主键索引上有，所以不得不回表。那么，有没有可能经过索引优化，避免回表过程呢？
覆盖索引
如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经覆盖了我们的查询需求，我们称为覆盖索引
需要注意的是，在引擎内部使用覆盖索引在索引 k 上其实读了三个记录，ID3、ID4、ID5（对应的索引 k 上的记录项），但是对于 MySQL 的 Server 层来说，它就是找引擎拿到了两条记录，因此 MySQL 认为扫描行数是 2。
由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段，基于上面覆盖索引的说明，我们来讨论一个问题：在一个市民信息表上，是否有必要将身份证号和名字建立联合索引？
CREATE TABLE `tuser` ( `id` int(11) NOT NULL, `id_card` varchar(32) DEFAULT NULL, `name` varchar(32) DEFAULT NULL, `age` int(11) DEFAULT NULL, `ismale` tinyint(1) DEFAULT NULL, PRIMARY KEY (`id`), KEY `id_card` (`id_card`), KEY `name_age` (`name`,`age`), KEY `id_card_name` (`id_card`,`name`) //联合索引 ) ENGINE=InnoDB
我们知道，身份证号是市民的唯一标识。也就是说，如果有根据身份证号查询市民信息的需求，我们只要在身份证号字段上建立索引就够了。而再建立一个（身份证号、姓名）的联合索引，是不是浪费空间？
如果现在有一个高频请求，要根据市民的身份证号查询他的姓名，这个联合索引就有意义了。例如这个sql：select name from T where id_card =500
它可以在这个高频请求上用到覆盖索引，不再需要回表查整行记录，减少语句的执行时间。给id_card 和 name建立联合索引后，name的值也会被保存在id_card索引树的节点上，这样根据给定id_card的值找到的对应行时，就可以直接获取到name了，而不需要拿着对应的主键再进行回表操作。
需要注意，覆盖索引不能只覆盖要查询的列，同时必须将WHERE后面的查询条件的列都覆盖，也就是这个联合索引要包含查询条件和返回的查询列。
