Schema的优化和索引 - 索引的基础 - 索引的类型 - B-Tree索引

索引的类型

索引有许多类型，它们都是针对不同的用途而被设计的。索引是在存储引擎中实现的，而不是服务器。因此它们并没有标准化：在每个引擎中，索引工作的方式都有所不同，并且并不是所有的存储引擎支持所有种类的索引。即使这些存储引擎支持索引的类型相同，在底层的实现也是有所不同。

 

让我们来看看MySQL所支持的索引类型，它们的优势和缺点。

 

B-Tree索引

当人们讨论索引而没有说明它的类型的时候，往往指的是B-Tree索引。它用B-Tree数据结构存储了数据。大部分MySQL存储引擎都支持这种类型。Archive引擎是个例外：MySQL5.1之前还不支持索引，现在可以支持对AUTO_INCREMENT列添加一个索引了。

 

对于这些索引，我们使用术语B-TREE，那是因为在CREATE TABLE和其他语句中MySQL都是这么使用它们的。然而，存储引擎内部可能使用不同的存储结构。比如，NDB集群存储引擎使用T-TREE的结构来实现这些索引的。

 

存储引擎在硬盘上存储B-TREE索引的方式也各不相同。这些方式会影响性能。举个实例，MyISAM使用前缀压缩技术使索引变得更小。然而InnoDB并没有压缩索引，因为它的一些优化功能不能使用压缩的索引。MyISAM还通过行所存储的物理位置来引用这个已索引的行，但是InnoDB是通过主键值来引用它们的。每种方式都有各自的优点和缺点。

 

B-Tree的普通思路是，有序的存储所有的值，并且每个叶的页面(leaf page)和根节点都是相同的距离。下面的图是抽象的B-Tree索引的展现。这和InnoDB索引的工作方式有点相吻合。（InnoDB使用的是B+TREE结构）。MyISAM使用不同的结构，但是概念上是相似的。

 

因为存储引擎不必为了查找所需的数据而检索这张表，所以一个B-Tree的索引能加快数据的访问。相反，它是从根节点开始查找。（图中并没有表示）。根节点的槽（slots）保存了指向子节点的指针，并且此存储引擎也关注这些指针。它通过 查看节点页面的值来找到正确的指针。在子节点中定义了值的最大和最小的范围。最终，存储引擎就会知道查找的值是否存在。

 

叶的页面（leaf page）是特殊的，因为它们有指针指向索引数据，而不是指向其他页。（不同的存储引擎有不同的指针类型指向数据）。我们的例子展示了只有一个节点页和它的页的页面(leaf page)，但是实际上在根节点和叶之间有很多级别的节点。树的深度取决于表的大小。

 

因为B-Trees存储了有序的索引列。所以对于搜索某一范围的数据是很有用的。来看一个示例，来看一个文本字段加上一个以字母顺序排序的索引的层级树，因此来查询“首字母的范围是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列的值。存储的图如下：

 

 要注意的是，索引存储的值的顺序是在表定义的时候所给定的列的顺序。来看看最后两个实体：这两个人有相同的名字，而生日不同，因此他们是通过生日来存储的。

 

可以使用B-Tree索引的查询类型

B-Tree可以很好的用于查找所有键的值（full key value）,一个键的范围（a key range），或者一个键的前缀（a key prefix）。但是这个查找仅仅适用于索引的最左边的前缀。我们前一步所讲到的索引可以适用于下面类型的查询

 

匹配所有的值

对于索引中所有的列，匹配所有键的值。举个例子，索引可以帮助你找到一个出生于1960-01-01名字叫Cuba Allen的人。

 

匹配最左端的前缀

索引可以帮助你找到last_name为Allen的所有的人。前提是，last_name必须为索引的第一个列。

 

匹配一个列的前缀

你可以匹配一个列值的第一个部分。也就是这个索引可以帮助你查找last_name的首字母为J的所有用户。前提是 last_name必须为索引的第一个列。

 

匹配一个范围的值

索引可以帮助找到last_name范围为Allen和Barrymore的所有用户。前提还是 last_name必须为索引的第一个列。

 

准确匹配一部分并且匹配另一个部分的一个范围

这个索引可以帮助你查找last_name为Allen并且first_name首字母为K的用户。这个就是精确匹配last_name以及在first_name上的一个范围查询。

 

仅支持索引的语句(Index-only queries)

B-Tree索引能支持一般的仅支持索引的语句(Index-only)。这些语句是只能通过索引来访问的语句,而不是通过行存储。以后将会详细说到。

 

 

因为树的节点是有序的，因此它们可以用于查找和ORDER BY语句。一般来说，如果一个B-Tree能帮助使你通过特定的条件找到一个行，它也能在相同的条件下排序这些行。因此，我们的索引对于ORDER BY是有用的，当然前提是要符合我们上述所列出的查询类型。

 

下面是一些B-Tree索引的限制

1.如果查找不从索引最左边的列开始，这些索引就没用了。举个例子，当你要查找name为bill或者指定的birthday的时候，它们就没啥用处了，因为这些列都不是在索引的最左边。同样的，你也不能使用索引查找last_name列中，以指定字母结尾的用户。

 

2.在索引中你不能跳过列。也就是说，你将不能查找last_name为Smith和指定的birthday。如果你不指定first_name，那么MySQL只会对第一列使用索引。

 

3.存储引擎不能优化那些在首个范围条件列的右边的任意列。举个例子，如果你的查询是WHERE last_name="Smith" AND first_name LIKE 'J%' AND dob='1976-12-23‘。索引只会应用在前两个列，因为Like是个范围条件。对于有限制值数量的一个列，你可以通过指定相同条件的方法取代范围条件。在以后的索引示例中将会详细说到。

 

通过上面的学习，你可以知道为什么列的顺序是如此重要了把。这些限制都是关于列的顺序的。对于一个高性能的应用。你可能需要创建相同的列但是不同顺序的一些索引来满足你的查询。

 

有一些限制并不是来自于B-Tree索引的，而是由MySQL语句优化的方式和存储引擎如何使用索引所产生的。其中的一些在未来的MySQL版本中可能就不是限制了。