1. Index

二叉树

红黑书：self-balancing binary search tree

2.Leftmost prefix principal

简述什么是最左匹配原则

最左匹配原则（leftmost prefix principle）是在使用MySQL联合索引的时候，需要遵循的规则，否则会导致联合索引失效。

规则

大多索引在MySQL都是b+树的数据结构，联合索引在b+树中每个节点都是一个复合的数据结构。在包含多个字段的联合索引中，能用上索引的查询有以下：仅包含第一个字段，包含前两个字段，或者包含前三个字段等等。

字段的最左匹配

比如现在有一个联合索引：(name,age,sex)，MySQL会根据从左到右的顺序建立b+树。

场景1

如果现在查询(ZhangSan,16,F)这个数据，过程如下：

• b+树首先会比较name字段来决定下一步的搜索方向（选择哪个子节点）。
• 如果name相同，接下来比较age字段。
• 如果age也相同，再比较sex字段...直到找到数据为止。

场景2

但是，如果要查询条件是(16,F)，没有name字段，那MySQL一开始就不知道应该选择哪个节点了。因为索引树在建立的时候，name字段就是第一个比较因素。因此，类似(16,F)，(16)，(F)等查询条件，这个联合索引都会失效。