B-Tree索引案例分析
如果将数据放入磁盘中，由于指令的执行速度远远超过磁盘的读写速度，因此控制运行时间的几乎都是磁盘访问次数。那么写一个复杂的程序来将磁盘访问次数降低到一个很小的常数是很有意义的。 B－Tree：所有的数据项都存储在树叶上，每一个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历。B－Tree通常意味着所有的值都是按顺序存储的，并且每一个叶子页(每个叶子页包含多个树叶)到根的距离相同，很适合查找范围数据。（ InnoDB使用的是B Tree）
注意叶子页中的每一个节点，保存了数据的值、指向数据的指针(数据的物理地址，对innodb，由于使用聚簇索引，指定primary key的值即可)和指向下一个节点或者下一个叶子页的链接。 可以利用B-Tree索引进行全关键字、关键字范围和关键字前缀查询，当然，如果想使用索引，你必须保证按索引的最左边前缀(leftmost prefix of the index)来进行查询。由于B 树中的节点都是顺序存储的，所以可以利用索引进行查找(找某些值)，也可以对查询结果进行ORDER BY。
2.3.2、Hash索引
哈希索引基于哈希表实现。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样，如果多个值有相同的hash code，索引把它们的行指针用链表保存到同一个hash表项中。哈希索引将所有的哈希存储在索引中，同时在哈希表中保存指向每个数据的指针。 MySQL中，只有Memory存储引擎显示支持hash索引，是Memory表的默认索引类型，尽管Memory表也可以使用B-Tree索引。 InnoDB引擎有一个特殊的功能叫做“自适应哈希索引（adaptive hash index)”。当 InnoDB注意到某些索引值被使用得非常频繁时，它会在内存中基于B-Tree索引之上再创建一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速的哈希査找。这是一个完全自动的、内部的行为，用户无法控制或者配置，不过如果有必要， 完全可以关闭该功能。 优点：访问十分迅速，同时Hash值不取决于列的数据类型，一个TINYINT列的索引与一个长字符串列的索引一样大。 缺点：不能使用hash索引排序。Hash索引只支持等值比较。那就很难查询范围和排序。也不能部分匹配，那就不能模糊查询。
2.3.3、空间(R-Tree)索引
MyISAM支持空间索引，主要用于地理空间数据类型，例如GEOMETRY。
2.3.4、全文(Full-text)索引
全文索引是MyISAM的一个特殊索引类型，它查找的是文本中的关键词主要用于全文检索，对中文意义不大。InnoDB存储引擎从1.2.x版本开始支持全文检索的技术，其采用full inverted index 的方式。全文检索通常使用倒排索引（inverted index)来实现。它在辅助表中存储了单词与单词自身在一个或多个文裆中所在位置之间的映射。这通常利用关联数组实现，其拥有两种表现形式：
- inverted file index，其表现形式为{单词，单词所在文档的ID}
- full inverted index,其表现形式为{单词，（单词所在文档的ID,在具体文档中的位置)}
