了解下B-tree索引

了解下B-tree索引

当人们讨论索引的时候，如果没有特别指明类型，那多半说的是B-tree索引，他使用B-tree数据结构来存储数据，大多数MYSQL引擎都支持这种索引，Archive引擎是一个例外：5.1之前Archive不支持任何索引，直到5.1才开始支持单个自增列（AUTO_INCREMENT）的索引。

我们使用术语“B-Tree”，是因为MySQL在CREATE TABLE和其他语句中也使用该关键字。不过，底层的存储引擎也可能使用不同的存储结构，例如，NDB集群存储引擎内部实际上使用了T-tree结构存储这种索引，即使期名字是BTREE;InnoDB则使用的是B+Tree，各种数据结构和算法的变种在这里不讨论。

存储引擎以不同的方式使用B-Tree索引，性能也各有不同，各有优劣。例如，MyISAM使用前缀压缩技术使得索引更小，但InnoDB则按照原数据格式进行存储，再如MyISAM索引通过数据的物理位置引用被索引的行，而InnoDB则根据主键引用被索引的行。

B-Tree通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。下图展示了B-Tree索引的抽象表示，大致反映了InnoDB索引是如何工作的。MyISAM使用的结构有所不同，但基本思想是类似的。

B-Tree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值找到合适的指针进行下层子节点，这些指针实际上定义了子节点中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。叶子节点比较特别，他们的指针指向的是被索引的数据，而不是其他的节点页（不同引擎的“指针”类型不同）。上图仅绘制了一个节点和其对应的叶子节点，其实在根节点和叶子节点之间可能有很多层节点页。树的深度和表的大小直接相关。

  BTree对索引列是顺序组织存储的，所以很适合查找范围数据。例如，在一个基于文本域的索引树上，按字母顺序传递连续的值进行查找是非常合适的，所以像“找出所有以I到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列的值，下图显示了该索引是如何组织数据的存储的。

请注意，索引对多个值进行排序的依据是CREATE TABLE语句中的定义索引时列的顺序，看下面最后两条目，两个人的姓和名都一样，则根据他们的出生日期来排序顺序。

可以使用B-Tree索引的查询类型，B-Tree索引适用于全键值，键值范围或键前缀查找。其中键前缀查找只适用于根据最左前缀的查找。前面所述的索引对如下类型的查询有效。

*全值匹配

*匹配最左前缀

*匹配列前缀

*匹配范围值

*精确匹配某一列并范围匹配另外一列

因为索引树中的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的ORDER BY操作（按顺序查找）。一般来说，如果B_TREE可以按照某种方式查找到值，那么也可以按照这种方式用于排序。所以，如果order by子句满足前面列出的几种查询类型，则这个索引也可以满足对应的排序需求。

下面是一些关于B_TREE索引的限制

1:如果不是按照索引的最左列开始查找，则无法使用索引。例如上面例子中的索引无法用于查找名字为BILL的人，也无法查找某个特定生日的人，因为这两列都不是最左数据列。类似地，也无法查找姓氏以某个字母结尾的人。

2：不能跳过索引中的列，也就是说，前面所述的索引无法用于查找姓为Smith并且在某个特定日期出生的人。如果不指定名（first_name）,则MYSQL只能使用索引的第一列。

3：如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。例如哟查询where last_name=’Smith’ AND first_name Like ‘J%’ AND dob =’1976-12-23’，这个查询只能使用索引的前两列，因为这里LIKE是一个范围条件（但是服务器可以把其余列用于其他目的）。如果范围查询列值的数量有限，那么可以通过使用多个等于条件来代替范围条件。

到这里，前面提到的索引列的顺序是多么的重要：这些限制都和索引列的顺序有关。在优化性能的时候，可能需要使用相同的列但顺序不同的索引来满足不同类型的查询需求。

也有些限制并不是B-Tree本身导致的，而是Mysql优化器和存储引擎使用索引的方式导致的，这部分限制在未来的版本中可能就不再是限制了。

作者：黑马程序员JavaEE培训学院
首发：http://java.itheima.com/