《MySQL系列》索引小记

索引（index）是在存储引擎（storage engine）层面实现的，而不是Server层面。不是所有的存储引擎都支持所有的索引类型。即使多个存储引擎支持某一索引类型，它们的实现和行为也可能有所差别。

一、索引结构（物理存储）

1. 聚簇索引

将数据存储与索引放在一块，找到索引也就找到了数据。

2. 非聚簇索引

将数据存储与索引结构分开，索引结构的叶子结点指向了数据的对应行。

来自《高性能MySQL》

InnoDB

使用的是聚簇索引，在聚簇索引之上创建的索引称之为辅助索引，辅助索引访问数据总是需要二次查找，辅助索引叶子结点存储的不再是行的物理位置，而是主键值。

将主键组织到一棵B+树中，而行数据就储存在叶子节点上，若使用”where id = 14″这样的条件查找主键，则按照B+树的检索算法即可查找到对应的叶节点，之后获得行数据。

若对Name列进行条件搜索，则需要两个步骤：第一步在辅助索引B+树中检索Name，到达其叶子节点获取对应的主键。第二步使用主键在主索引B+树种再执行一次B+树检索操作，最终到达叶子节点即可获取整行数据。（重点在于通过其他键需要建立辅助索引）

MyISAM

使用的是非聚簇索引，非聚簇索引的两棵B+树看上去没什么不同，节点的结构完全一致只是存储的内容不同而已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独立的，通过辅助键检索无需访问主键的索引树。

通过key_buffer把索引先缓存到内存中，当需要访问数据时（通过索引访问数据），在内存中直接搜索索引，然后通过索引找到磁盘相应数据，这也就是为什么索引不在key buffer命中时，速度慢的原因。

覆盖索引

指一个查询语句的执行只用从非主键索引中就能查到的记录，而不需要查询主键索引中的记录，避免了回表的产生减少了树的搜索次数，显著提升性能。

（当发起一个索引覆盖查询时，在explain的extra列可以看到using index的信息）

二、索引存储类型（数据结构）

1. B+树索引

• 1. 二叉查找树：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表
• 2. 平衡二叉树：通过旋转解决了平衡的问题，但是旋转操作效率太低
• 3. 红黑树：通过舍弃严格的平衡和引入红黑节点，解决了平衡二叉树旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多。
• 4. B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题。
• 5. B+树：在B树的基础上，将非也节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查找更加高效

当数据在磁盘中时，磁盘 IO 会成为最大的性能瓶颈，设计的目标应该是尽量减少 IO 次数；而树的高度越高，增删改查所需要的 IO 次数也越多，会严重影响性能。

2. Hash索引

3. Fulltext索引

（现在MyISAM和InnoDB引擎都支持）

4. R-Tree（空间）索引

用于对GIS数据类型创建SPATIAL索引。只有MyISAM引擎支持，并且支持的不好。可以忽略

三、索引类型（逻辑角度）

1. 主键索引

2. 普通索引、单列索引

3. 多列索引（组合索引）

4. 唯一索引、非唯一索引

5. 空间索引

等哪天想起来了继续补充。。。