B-Tree索引

树的结构不详细分析 ，不同的存储引擎用的索引存在差异。

B-Tree索引

B-Tree索引

如图便是B-Tree索引的结构，特点：

• 所有的值都是按照顺序存储（根节点17、35两个关键字划分三个区域，不同区域指针指向子结点，便于查找）
• 每个关键字上都带有需要查找的数据

B+Tree索引

B+Tree索引

InnoDB存储引擎就是使用的B+Tree索引。是在B-Tree索引上的一种优化，特点：

• 非叶子结点只存储键值
• 所有的数据记录都存在叶子结点中
• 叶子结点中间都有一个链指针

叶子结点间加链指针目的：方便区间访问的性能。例如访问 15到28之间的数据，便可以在找到15后直接顺着指针遍历就可以找到，提高了区间访问效率。

B-Tree索引适用的范围：

例如有如下表：

name	country	age
Jane	Cuba	14
Ming	Japan	23
David	Canada	20

将(name,country,age)构成索引

1. 全值匹配：对索引中所有列指定具体值，例如：Jane Cuba 14
2. 匹配最左前缀：当查询条件精确匹配索引的左边连续一个或几个列时，例如(name),(name,country)，可以用到。
3. 匹配列前缀：匹配某一列的值得开头部分。例如 name like Ja% , 对于 name like %ne 这种就很抱歉了，没办法使用索引了。
4. 匹配范围值：范围列可以用到索引（必须是最左前缀），但是范围列后面的列无法用到索引。（l例如 where name ='Jane' and country like 'Cu%' and age = 14 ,这种情况下，age就无法使用到索引了，country这块是使用了一个范围查询）
5. 精确匹配某一列，范围匹配另一列：例如 name= 'Jane' and country like 'Cu%'
6. 只访问索引: 查询的列都在索引中。

注意：

1. 查询必须从索引最左列开始，例如不能直接利用索引查找某个年龄的人
2. 不能跳过某一索引列，例如查找name = 'Jane' 且 age = 14 的人，就用不到索引
3. 范围条件右边的列，无法使用索引。例如上面的匹配范围值的例子。