MySQL索引数据结构入门( 三 ) _MySQL

1170*1170*16=21902400
可以存储 2100万条数据。
在 InnoDB 存储引擎中，B+Tree 的高度一般为 2-4 层，这就可以满足千万级的数据的存储，查找数据的时候，一次页的查找代表一次 IO，那我们通过主键索引查询的时候，其实最多只需要 2-4 次 IO 操作就可以了。
2.3 什么样的搜索可以用到索引？根据前面的介绍，我们可以得出结论，在以下类型的搜索中，会用到索引：

全值匹配

如上图中，如果我们要搜索 username 为 ac 且 age 为 98 的用户，就可以直接使用索引精确定位到。

最左匹配

如果我们只是想搜索 username 为 ac 的用户，很明显也可以使用上图索引，因为用户名是有序的。在上图中，username 和 age 组成了联合索引，其中 username 在前，age 在后，所以索引是先按照 username 进行排序，username 相同的时候，再按照 age 进行排序的（如 bw 这个用户），如果我们按照 username 进行搜索，那么没问题，可以用上索引；但是如果我们按照 age 进行搜索，很明显，age 在整个索引树中是无序的，所以当我们使用 age 作为搜索条件的时候，是没法使用上图这个联合索引的。

前缀匹配

如果我们搜索的关键字只是 username 字段的前半部分，那么很明显，也是可以使用索引的，例如搜索所有以 a 开始的 username 。

范围匹配

如果我们的搜索条件是一个范围，很明显也可以使用到上述索引，例如搜索姓名介于 ab～cc 之间的用户，只需要先从索引树的根节点开始，先找到 ab，然后根据叶子节点之间的指针顺藤摸瓜，找到 cc 之后的第一个数据（不满足条件的第一个数据）结束。

前面全值匹配，后面范围匹配

例如查找 username 为 bw 且 age 介于 90～99 之间的用户，这种情况也可以使用到上图的索引。在上图索引树中，当 username 相同的时候，就是按照 age 排序的，所以对于 username 都为 bw 的用户，它就是按照 age 进行排序的，此时，我们当然可以按照 age 的范围进行搜索了。

覆盖索引

有的时候，我们搜索的数据都在索引树中了，例如上图中的索引，我们想搜索 username 为 bw 的用户的 age，由于 age 就在索引树中，直接返回即可，这就是覆盖索引了。
2.4 使用限制毫无疑问，基于 B+Tree 的索引，其实也存在一些使用限制。例如：

如果我们将 age 作为搜索条件，虽然 age 也是联合索引的一部分，但是 age 整体上在索引树中是无序的，所以将 age 作为搜索条件是没法使用上述索引的。
基于第一点，如果联合索引中还有第三、第四列等，那么凡是跳过第一列直接使用后面的列作为查询条件，索引都是不会生效的。
范围条件的右边无法使用索引直接定位。例如搜索 username 以 a 开头并且年龄为 99 的用户：where username like 'a%' and age=99，此时 age=99 这个条件就无法在索引树中直接处理了（可以通过索引下推过滤）。原因很简单，当我们找到所有 username 以 a 开始的用户之后，这些用户的 age 并不是有序的，所以 age 就没法继续使用索引搜索了（但是可以通过索引下推过滤）。

关于第三点，我举一个例子，假设我们还有两个用户，分别是：

username 为 ad 且 age 为 80；
username 为 ae 且 age 为 88；

那么我们完善一下上面 B+Tree 的图应该变成下面这样：

文章插图
可以看到，username 以 a 开始的用户，age 并不是有序的，所以就只能通过索引下推过滤了，而无法直接通过索引扫描定位数据。
对于第三点，如果范围搜索的字段值的可能性比较少，则可以通过多个等于比较来代替范围搜索。
2.5 自适应哈希索引Hash 索引在 MySQL 中主要是 Memory 和 NDB 引擎支持，InnoDB 索引本身是不支持的，但是 InnoDB 索引有一个特性叫做自适应哈希索引，自适应三个字意味着整个过程是全自动的，不需要开发者配置。
当 InnoDB 监控到某些索引值被频繁的访问时，那么它就会在 B+Tree 索引之上，构建一个 Hash 索引，进而通过 Hash 查找来快速访问数据。