B 树索引概述

Mysql InnoDB 引擎默认使用的索引数据结构是 B+ 树，不过这里仍使用“B 树”术语来代替，因为 Mysql 在 create table 和其他语句中也使用该关键字，而且 Mysql 中的索引是在存储引擎层而不是服务器层实现的，所以并没有统一的索引标准，底层的存储引擎也可能使用不同的存储结构。
存储引擎以不同的方式使用 B 树索引。例如，MyISAM 使用前缀压缩技术使得索引更小，但 InnoDB 则按照原数据格式进行存储。再如 MyISAM 索引通过数据的物理位置引用被索引的行，而 InnoDB 则根据主键引用被索引的行。
B 树通常意味着所有的值都是按照顺序存储的，并且每一个叶子到根的距离都相同。因为 B 树对索引列是顺序存储的，所以很适合查找范围数据。
假设有这样一张表：

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 列的值。下图显示了该索引是如何组织数据的存储的。
[img]http://dl2.iteye.com/upload/attachment/0127/8829/77064a2e-357e-3f0b-8a91-050a00ff7d35.png[/img]
索引对多个值进行排序的依据是 CREATE TABLE 语句中定义索引时列的顺序。B 树索引适用于全键值、键值范围或键前缀查找，其中键前缀查找只适用于根据最左前缀的查找。这里所说的索引对如下类型的查询有效。
（1）全值匹配，指的是和索引中的所有列进行匹配。
（2）匹配最左前缀，例如上面的索引可用于查找所有姓为 Allen 的人。
（3）匹配列前缀，即只匹配某一列的值的开头部分。例如上面的索引可用于查找所有以 J 开头的姓的人。
（4）匹配范围值，例如上面的索引可用于查找所有姓在 Allen 和 Barrymore 之间的人。
（5）精确匹配某一列并范围匹配另外一列，例如上面的索引可用于查找所有姓为 Allen 并且名字以 K 开头的人。
因为索引树中的节点是有序的，所以索引还可用于 ORDER BY 操作，只要它满足上面列出的这几种查询类型，那么这个索引就可以满足对应的排序需求。
不过 B 树索引也有这样一些限制：
（1）如果不是按照索引的最左列开始查找，则无法使用索引。
（2）不能跳过索引中的列。例如上面的索引无法用于查找姓为 Smith 并且咋某个特定日期出生的人。如果不指定 first_name，则 mysql 只能使用索引的第一列。
（3）如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。例如查询条件“WHERE last_name='Smith' AND first_name LIKE 'J%' AND dob='1976-12-23'”将只能使用索引的前两列，因为这里的 LIKE 是一个范围条件（但是服务器可把其余列用于其他目的）。
由此可见索引列的顺序非常重要，优化性能的时候也是应该考虑的。