MySQL 索引之 B-Tree 索引

这周在开发中遇到了一些关于联合索引的问题，导致了在数据库中查询的时候对性能造成了很大的影响。

问题大概是这样的，有一张 posts 表，里面有 user_id 和 activity_id 两个字段，分别表示 post 的创建者和所属的活动。现在有两个常用的查询需求，分别是 查找某个用户的所有 posts 以及 查找某个活动的所有 posts。当时我很想当然的创建了一个 [userid, activityid] 的联合索引，心想着这样就不需要对两个字段单独创建索引，不是省了一组索引吗，多好。。。结果，大错特错。

先来看看联合索引的具体的用途:

• 全值匹配

对于上面建立的索引来说，我们可以查询 user_id 为 ? 同时 activity_id 为 ? 的 posts

• 匹配最左前缀

即查询 user_id 为 ? 的 posts

• 匹配列前缀

这里我们我们上面的内容不适用，假设还有一个 user_name 字段，存储 post 的用户名，我们可以利用这个索引来查询以 A 或者 B 之类开头的用户的 posts

• 匹配范围值

我们可以查询 user_id 为 ? ~ ? 用户的 posts

• 精确匹配某一列并范围匹配另一列

我们可以查询 user_id 为 ? 的用户在 activity_id 为 ? ~ ? 的活动发的所有 posts

不能实现的查询

• 不按照索引的顺序

比如需要查找 activity_id 为 ? 的所有 posts 是不能实现的

• 跳过索引中的列

假如我们的联合索引中有三个字段 [A, B, C]，我们想要跳过 B 来查询和 A、C 条件相关的内容也是不能利用索引的

• 两个列都范围查询

假设我们查询 user_id 为 ? ~ ? 的 posts，这时如果我们还想加上条件说 activity_id 也要在某个范围，这时也是无法利用索引的

好了，大概就是这么多的应用了，其实以前也是看过书里讲这个的。但是由于理解的不深刻没多久就忘了，这次就又犯这个错误了。这次就干脆花点时间来深究一下以上罗列的几条到底是为什么?

WHY

简单的来说，这和索引背后的数据结构有关系，我们知道 MySQL 实现索引通常是适用的 B-Tree (B+Tree)，对于单列的索引我们很好理解。那么多列的索引，它的具体一个结构是怎么样的呢?

还是以上面的表的联合索引为例子，我画了一个简单的图来表示这个联合索引存储的大致的数据结构是什么样子的

可以看到，其实这个索引最后存储的结构还是先以 user_id 为 primary key (这么说好像不太合适) 来构建这个 tree 的，所以当我们查询的时候如果只用 activity_id 或者是颠倒顺序来，我们都没有这个数据结构的入口，自然也没法利用它来为我们提高效率了。