mysql 索引类型详解-B-Tree索引

文章标签: mysql,b-tree
2015-1-5 17:40:52     51 人阅读    

        索引有很多种类型,可以为不同的场景提供更好的性能。在MySQL中,索引是在存储 引擎层而不是服务器层实现的。所以,并没有统一的索引标准:不同存储引擎的索引的 工作方式并不一样,也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎 支持同一种类型的索引,其底层的实现也可能不同。 下面我们先来看看MySQL支持的索引类型,以及它们的优点和缺点。


B-Tree索引
        当人们谈论索引的时候,如果没有特别指明类型,那多半说的是B-Tree索引,它使用 B-Tree数据结构来存储数据a2。大多数MySQL引擎都支持这种索引。Archive引擎是 一个例外:5.1之前Archive不支持任何索引,直到5.1才开始支持单个自增列(AUT0_ INCREMENT)的索引。
我们使用术语“B-Tree”,是因为MySQL在CREATE TABLE和其他语句中也使用该关键字。

    

      不过,底层的存储引擎也可能使用不同的存储结构,例如,NDB集群存储引擎内部实际 上使用了 T-Tree结构存储这种索引,即使其名字是BTREE ; InnoDB则使用的是B+Tree, 各种数据结构和算法的变种不在本书的讨论范围之内。


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


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

      B-Tree索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取需要 的数据,取而代之的是从索引的根节点(图示并未画出)开始进行搜索。根节点的槽中 存放了指向子节点的指针,存储引擎根据这些指针向下层査找。通过比较节点页的值和 要査找的值可以找到合适的指针进入下层子节点,这些指针实际上定义了子节点页中值 的上限和下限。最终存储引擎要么是找到对应的值,要么该记录不存在。
        

       叶子节点比较特别,它们的指针指向的是被索引的数据,而不是其他的节点页(不同引 擎的“指针”类型不同)。图5-1中仅绘制了一个节点和其对应的叶子节点,其实在根节 点和叶子节点之间可能有很多层节点页。树的深度和表的大小直接相关。
     

     B-Tree对索引列是顺序组织存储的,所以很适合査找范围数据。例如,在一个基于文本 域的索引树上,按字母顺序传递连续的值进行査找是非常合适的,所以像“找出所有以 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、fi「st_name和dob列的值,图5-2显 示了该索引是如何组织数据的存储的。

 

          请注意,索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。看<3ID 一下最后两个条目,两个人的姓和名都一样,则根据他们的出生日期来排列顺序。
          可以使用B-Tree索引的查询类型。B-Tree索引适用于全键值、键值范围或键前缀査找。
          其中键前缀查找只适用于根据最左前缀的査找&3。前面所述的索引对如下类型的査询有 效。
全值匹配
全值匹配指的是和索引中的所有列进行匹配,例如前面提到的索引可用于查找姓名 为 Cuba Allen、出生于 1960-01-01 的人。
匹配最左前缀
    前面提到的索引可用于査找所有姓为Allen的人,即只使用索引的第一列。
匹配列前缀
    也可以只匹配某一列的值的开头部分。例如前面提到的索引可用于査找所有以J开 头的姓的人。这里也只使用了索引的第一列。
匹配范围值
例如前面提到的索引可用于査找姓在Allen和Barrymore之间的人。这里也只使用 了索引的第一列。
精确匹配某一列并范围匹配另外一列
前面提到的索引也可用于査找所有姓为Allen,并且名字是字母K开头(比如Kim、Karl等)的人。即第一列llast_name全匹配,第二列first_name范围匹配。

只访问索引的查询
    B-Tree通常可以支持“只访问索引的査询”,即査询只需要访问索引,而无须访问 数据行。后面我们将单独讨论这种“覆盖索引”的优化。
     因为索引树中的节点是有序的,所以除了按值査找之外,索引还可以用于査询中的 ORDER BY操作(按顺序査找)。一般来说,如果B-Tree可以按照某种方式査找到值,那 么也可以按照这种方式用于排序。所以,如果ORDER BY子句满足前面列出的几种査询类 型,则这个索引也可以满足对应的排序需求。

下面是一些关于B-Tree索引的限制:
•       如果不是按照索引的最左列开始査找,则无法使用索引。例如上面例子中的索引无<313 法用于査找名字为Bill的人,也无法査找某个特定生日的人,因为这两列都不是最 左数据列。类似地,也无法査找姓氏以某个字母结尾的人。
不能跳过索引中的列。也就是说,前面所述的索引无法用于査找姓为Smith并且在 某个特定日期出生的人。如果不指定名(first_name),则MySQL只能使用索引的第一列。

 
       如果查询中有某个列的范围查询,则其右边所有列都无法使用索引优化査找。例如 有査询WHERE last_name=,Smith' AND fi「st_name LIKE 'J%_ AND dob = 11976- 12-231,这个査询只能使用索引的前两列,因为这里LIKE是一个范围条件(但是服 务器可以把其余列用于其他目的)。如果范围査询列值的数量有限,那么可以通过使 用多个等于条件来代替范围条件。在本章的索引案例学习部分,我们将演示一个详 细的案例。
   

       到这里读者应该可以明白,前面提到的索引列的顺序是多么的重要:这些限制都和索引 列的顺序有关。在优化性能的时候,可能需要使用相同的列但顺序不同的索引来满足不 同类型的査询需求。 也有些限制并不是B-Tree本身导致的,而是MySQL优化器和存储引擎使用索引的方式 导致的,这部分限制在未来的版本中可能就不再是限制了。


原文地址:http://www.itmmd.com/201501/443.html
该文章由 萌萌的IT人 整理发布,转载须标明出处。

jQuery教程(9)-DOM树操作之复制元素   上一篇
下一篇  jQuery教程(8)-DOM树操作之使用反向插入方法

精彩回复
发表评论
姓名:       

《程序员app》专门为程序员量身定做!