首页 > 技术笔记 > MySQL > MySQL读书笔记——索引类型:B-Tree和哈希索引介绍
2015
11-21

MySQL读书笔记——索引类型:B-Tree和哈希索引介绍

索引是数据库优化中最常用、最有效也是最重要的手段之一,索引对于良好的性能非常关键,尤其是数据量非常大时候,索引对数据库的性能影响更加重要,而索引却又经常被忽略,甚至被误解,最近阅读了相关方面的书籍,好记性不如烂笔头,所以记录下来,写入博客。

一、索引分类

索引是在mysql的存储引擎层实现的,而不是在服务器层实现的。不同的存储引擎支持的索引不同,而同一种索引在不同存储引擎中的实现也不太一样。Mysql常见的索引有:
  1. B-Tree索引:最常见的索引类型,大部分存储引擎都支持。
  2. HASH索引:只有Memory引擎支持,使用的场景比较简单。
  3. R-Tree索引(空间索引):是MyISAM的一个特殊索引类型,主要用于地理空间数据类型,使用较少。
  4. Full-Text(全文索引):全文索引也是MyISAM的一个特殊索引类型,主要用于全文索引,InnoDB从Mysql 5.6版本开始提供对全文索引的支持。

二、B-Tree索引

大部分存储引擎都支持B-Tree索引,只有Archive引擎不支持该索引类型。InnoDB内部实际使用B+Tree结构存储这种索引。MyISAM使用前缀压缩技术使得索引更小,而InnoDB则按照原数据格式进行存储。MyISAM索引通过数据的物理位置引用被索引的行,而InnoDB则根据主键引用被索引的行。 B-Tree索引所有值都是按照顺序存储的,下图是B-Tree索引的抽象表示。 b-tree1 B-Tree索引能够加快数据访问速度,因为不需要进行全表扫描获取数据,而是从根节点开始搜索,根节点的槽中存放着指向子节点的指针,存储引擎再根据这些指针向下层搜索。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点,这些指针定义了子节点页中值得上限和下限,最终存储引擎要么找到对应的值,要么该记录不存在。叶子节点比较特别,它们的指针指向的是被索引的数据,而不是其他节点页。其实在根节点和叶子节点之间可能有多层节点页,树的深度与表的大小有关。 以下是一个B-Tree索引的一个示例: b-tree2 B-Tree存储引擎适用的场景:
  1. 匹配全值,对索引中所有列都指定具体值,即是对索引中的所有列都有等值匹配的条件。
  2. 匹配值的范围查询,对索引的值能够进行范围查找。
  3. 匹配最左前缀,仅仅适用索引中的最左边列进行查找,比如在col1+col2+col3字段上的联合索引能够被包含col1、(col1+col2)、(col1+col2+col3)的等值查询利用到,可是不能够被col2、(col2+col3)的等值查询利用到。
  4. 仅仅对索引进行查询,当查询的列都在索引的字段中时,查询的效率最高。
  5. 匹配列前缀,仅仅使用索引中的第一列,并且只包含索引第一列的开头一部分进行查找。
  6. 能够实现索引匹配部分精确而其他部分进行范围匹配。
  7. 如果列名是索引,那么使用column not null就会使用索引。
但是以下几种情况不会使用B-Tree索引:
  1. 如果不是按照索引的最左列开始查找,则无法使用索引。
  2. 不能跳过索引中的列。例如key(last_name,first_name,dob)索引,无法直接用于查找last_name为Smith并且某个特定日期出生的人,如果不指定first_name,则Mysql只能使用索引的第一列。
  3. 如果查询中有某个列的范围查询,则其右边所有列都无法使用索引优化查找。例如WHERE last_name=’Smith’ AND first_name LIKE ‘J%’ AND dob=’1976-12-23’,这个查询就只能使用过索引的前两列,因为LIKE是一个范围查询,如果需要优化的话,对于范围查询列值如果数量有限,则可以用IN的等于条件来代替范围查询。

三、 哈希索引

在Mysql中,只有Memory引擎显式支持哈希索引,Memory引擎是支持非唯一哈希索引的,如果多个列的哈希值相同,索引会以链表的方式存放多个记录指针到同一个哈希条目中。 哈希索引查找的速度特别快,然而哈希所有也有它的限制:
  1. 哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。
  2. 哈希索引数据并不是按照索引值顺序存储的,所以也无法用于排序。
  3. 哈希索引也不支持部分索引匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如在数据列(A,B)上建立哈希索引,如果查询只有数据列A,则无法使用该索引。
  4. 哈希索引只支持等值比较查询,包含=、IN()、<=>,也不支持任何范围查询。
  5. 访问哈希索引的数据非常快,除非有很多哈希冲突(不同的索引列值却又相同的哈希值)。当出现哈希冲突的时候,存储引擎必须遍历链表中所有的行指针,逐行进行比较,直到找到所有符合条件的行。
  6. 如果哈希冲突很多的话,一些索引维护操作的代价也会很多。例如,如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引,那么当从表中删除一行时,存储引擎需要遍历对应哈希值的链表中的每一行,找到并删除对应行的引用,冲突越多,代价越大。
最后编辑:
作者:射雕天龙
转载请注明:转载自射雕天龙的博客(http://blog.wangjunfeng.com)
捐 赠如果您觉得这篇文章有用处,请支持作者!鼓励作者写出更好更多的文章!

MySQL读书笔记——索引类型:B-Tree和哈希索引介绍》有 1 条评论

  1. 巴中热线 说:

    学习了,谢谢分享!

留下一个回复

你的email不会被公开。