二叉树（B-Tree）索引
如果没有明确指定索引类型，那大家一般都是指二叉树索引—通常使用二叉树数据结构存储索引数据。大多数的MySQL存储引擎都支持这种索引类型。但Archive引擎是一个例外，直到MySQL 5.1版本后才开始支持索引——通过自增列允许了单索引。
二叉树只是一个泛称，其实，不同的存储引擎会使用不同的存储结构。比如，NDB集群存储引擎使用了T-Tree数据结构，但是也称为BTREE，而InnoDB则使用了B+T树。存储引擎使用B-Tree的方式也各不相同，而这也会影响性能。例如，MyISAM使用了前置压缩技术来缩小索引的存储空间，而InnoDB并没有做压缩。MyISAM索引映射到数据行的物理存储位置，而InnoDB则是通过数据行的主键进行映射的。虽然方式不同，但是原理是相似的。
二叉树索引能够加速数据访问是因为存储引擎不需要在查找数据时做全表扫描。事实上，它首先在根节点查找。根节点的有一个区域存储指向子节点的指针，存储引擎根据这些指针查找数据。他在节点页（定义了子节点的上下边界值）中找到满足条件的指针。最终，存储引擎要么是找不到对应的节点，要不就是找到正确的叶数据页。
二叉树索引结构
InnoDB的B+树索引查找方式
叶数据页是一个特殊的节点，这是因为他们有指针指向索引对应的数据，而不是其他数据页的指针。
由于二叉树有序存储了索引列，因此对于范围搜索十分有用。例如，假设一个B+树中的姓名索引是按照字母的降序排序的。那对于查找姓名中以字母K开头将十分高效。假设有如下数据表：
CREATE TABLE people {
last_name varchar(50) not null,
first_name varchar(50) not null,
dob date not null,
gender enum(‘m’, ‘f’) not null,
key(last_name, first_name, dob)
}
索引会包含last_name，first_name和dob三列的值。下图展示了存储的方式：
B+树索引存储示例
注意存储引擎按照创建表的key中的字段次序依次建立索引，因此你会看到在最后面的Basinger Vivien （注上图应该是Viven少了一个i）。由于last_name和first_name都相同，因此存储引擎会按照日期进行排序。
二叉树在进行完整值匹配，范围查找，匹配前面部分值的查找情况下表现很好。但只适用于索引最左匹配的情况下（即从where条件的从左到右进行索引匹配，如果遇到没有索引或者索引失效的则右侧即便有索引也是无效的）。以下是基于刚刚创建的表的例子：
-
完整值匹配：即从索引列检索一个完整匹配的值，例如从Person表中查找姓名为Cuba Allen，生日为1960-01-01的人（即使用=查询）。
-
最左匹配：查找last_name为Allen的人，这只会在条件是放置在where条件最左侧的情况。
-
前缀匹配：可以查找匹配索引列前面部分值的数据。例如查找last_name以字母J开头的人。
-
范围查找：查找索引列处于一个区间的数据。例如查找last_name处于Allen和Barrymore之间的数据。
-
在一个列部分匹配而其他索引列精准匹配：例如查找last_name为Allen而first_name以字母K开头的数据。
-
索引查询：直接对索引列的查询，例如对索引列进行分组查询。
由于二叉树是有序排列的，因此对索引列按值查找或ORDER BY排序的效率都非常高。当然二叉树索引也会有一些限制：
-
查询条件不满足最左匹配：例如查找一个last_name以某个字符结尾的人。或者查找姓名为Bill或出生在指定日期的人。
-
不可以跳过索引包含的列：例如查询last_name为Smith且出生在指定日期的人。如果不指定first_name的值，那MySQL只会使用索引中第一列。
-
存储引擎不能使用范围搜索右侧后的索引：例如如下WHERE语句：
WHERE last_name="Smith" AND first_name LIKE 'J%' AND dob='1976-12-23'
则只有last_name和first_name会命中索引，而dob不会，这是因为first_name使用的LIKE查询属于范围查找，这会导致右侧的dob索引失效。
这就是为什么索引列的次序十分重要的原因了，为了优化查询，也许你需要创建具有不同次序但是相同列的索引。当然，这在以后的MySQL版本中也可能会优化。
网友评论