Mysql 索引理解 – 汪明鑫的个人博客

首先来聊一下索引的分类[按索引的数据结构分]：

分类	特性
B+tree 索引	具体的结构下文会重点讲解，此处提一下的是，同样是B-tree 索引，不同的存储引擎使用也是有所差异的，例如，MyISAM 使用前缀压缩技术使得索引更小，但InnoDB 则按照原数据格式进行存储。MyISAM索引通过数据的物理位置引用被索引的行，但InnoDB 则根据主键引用被索引的行。
哈希索引	基于hash 表实现得，只有精确匹配索引所有得列得查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码，哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。也就是说先找找到哈希码，然后通过对应的指针找到数据行。哈希码是有顺序的，但是对应的数据行不一定是顺序的。 1 哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。不过,访问内存中的行的速度很快,所以大部分情况下这一点对性能的影响并不明显。 2 哈希索引数据并不是按照索引值顺序存储的,所以也就无法用于排序。 3 哈希索引也不支持部分索引列匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的。 4 哈希索引只支持等值比较查询,包括=、IN()、<>(注意和<=>是不同的操作)。也不支持任何范围查询,例如 WHERE price>100 5 访问哈希索引的数据非常快,除非有很多哈希冲突(不同的索引列值却有相同的哈希值)。当出现哈希冲突的时候,存储引擎必须遍历链表中所有的行指针,逐行进行比较,直到找到所有符合条件的行。 6 如果哈希冲突很多的话,一些索引维护操作的代价也会很高。例如,如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引,那么当从表中删除一行时,存储引擎需要遍历对应哈希值的链表中的每一行,找到并删除对应行的引用,冲突越多,代价越大。 7 记住不要使用SHA1()和MD5()作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串,会浪费大量空间,比较时也会更慢。
空间数据索引 R-tree	MyISAM表支持空间索引,可以用作地理数据存储。和B-Tree索引不同,这类索引无须前缀查询。空间索引会从所有维度来索引数据。查询时,可以有效地使用任意维度来组合查询。必须使用 MySQL的GIS相关函数如 MBRCONTAINS()等来维护数据。 MySQL的GIS支持并不完善,所以大部分人都不会使用这个特性。开源关系数据库系统中对GIS的解决方案做得比较好的是 PostgreSQL的 PostGIS。
全文索引	全文索引是一种特殊类型的索引,它查找的是文本中的关键词,而不是直接比较索引中的值。全文搜索和其他几类索引的匹配方式完全不一样。它有许多需要注意的细节,如停用词、词干和复数、布尔搜索等。全文索引更类似于搜索引擎做的事情,而不是简单的 WHERE条件匹配。

索引从结构上来讲基本也就这几种，了解这几种足够了，还有其他的像树形索引等等，了解一下就行。

重点说一下B+ tree 索引：

首先什么是B- tree:

每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构:

在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。非叶子节点只存储键值信息。所有叶子节点之间都有一个链指针。数据记录都存放在叶子节点中。

可以看出，在所有叶子节点上，是组成的一种链式环结构，可以看成一个双向链表，因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。

也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿条记录。实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。此处就明白了比二叉树好在什么地方了。