MySQL索引类型及数据结构【笔记】

1 索引类型

返回面试宝典
主键索引（PRIMARY）:数据列不允许重复，不允许为NULL，一个表只能有一个主键。
唯一索引（UNIQUE）:数据列不允许重复，允许为NULL，一个表允许多个列创建唯一索引。
普通索引（INDEX）：基本的索引类型，没有唯一限制，允许为NULL值。
全文索引（FULLTEXT索引在MySQL5.6之后支持InnoDB，而之前的版本只支持MyISAM表）。

下文将介绍一些常见的数据结构，为了帮助理解示例和动画效果可以参考数据结构可视化网站

2 哈希

哈希索引的实现比较简单，它是基于哈希表来实现的，对于要索引的列，存储引擎会计算出一一对应的哈希码，然后把哈希码存放在哈希表中作为key，value值是指向该行数据的指针。
优势：
只需对比哈希值，因此速度非常快，性能优势明显；
限制：

1. 不支持任何范围查询，比如where price >150，因为是基于哈希计算，支持等值比较；
2. 哈希表是无序存储的，因此索引数据无法用于排序；
3. Hash索引不能用于部分索引键查询，即不能用于部分索引键的组合索引；
4. Hash索引在任何时候都不能避免Hash表扫描；
5. Hash索引在遇到大量Hash值相等的情况后性能并不一定就会比BTree索引高；对于哈希值大量相同的情况下，大量记录的指针信息都会存在同一个哈希值指向的链表中，这样定位一条记录就会全链表扫描比对键值，从而造成整体性能低下。

主流存储引擎不支持该类型，比如MyISAM和InnoDB。哈希索引只有Memory，NDB两种引擎支持。哈希索引是一种非常快的等值查找方法（注意：必须是等值，哈希索引对非等值查找方法无能为力），它查找的时间复杂度为常量，InnoDB采用自适应哈希索引技术，它会监控表上索引的使用情况，如果认为建立哈希索引可以提高查询效率，则自动在内存中的“自适应哈希索引缓冲区”建立哈希索引。

InnoDB引擎有一个特殊功能叫做自适应哈希索引，当InnoDB注意到某些索引值被使用的非常频繁时，它会在内存中基于BTree索引之上再创建一个哈希索引，这样就让BTree索引也具有哈希索引的一些优点了，比如：快速的哈希查找，这是一个全自动的，内部的行为，不能人工干预，用户无法控制或者配置，不过如果有必要，可以选择关闭这个功能（innodb_adaptive_hash_index=OFF，默认为ON）。

3 BTree

MyISAM和InnoDB都支持这种索引，因此说它是应用最广泛，最常用的一种索引方式，但是不同的存储引擎在具体实现时会稍有不同，比如MyISAM会使用前缀的方式对索引进行压缩，InnoDB则不会。
BTree只是底层的算法实现，唯一索引、主键索引、普通索引都是基于BTree索引算法的，只不过又有各自的特点。
B树是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。
BTree的特点：

1. 叶节点具有相同的深度，叶节点的指针为空；
2. 所有索引元素不重复；
3. 节点中的数据索引从左到右递增排列；
4. 每个节点都有data

BTree的缺点：

1. 如果data过大，一个节点存放的数据少，这样会导致树加深，这样也增加了IO次数；
2. 范围查询支持的不好；
   针对上述缺点就需要寻找新的数据结构，于是B+Tree树就出现了。

4 B+Tree

B+树是B树的一种变体，B+树上的叶子节点存储索引和响应记录或记录地址，叶子节点以上各层作为索引使用。B+树的查找与B树不同，当索引部分某个节点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字右边的指针向下，一直查到该关键字所在的叶子节点为止。
特点：

1. 非叶子节点不存储data，只存储索引，可以放更多的索引；
2. 叶子节点包含所有索引字段；
3. 叶子节点用指针连接，提高区间访问的性能。

优点：

1. 较B树横向存储的索引更多，这样可大量减少磁盘I/O的次数；
2. 能很好的支持范围查询，因为叶子节点之间有双向指针连接。

4 空间索引

空间索引可用于地理数据存储，它需要GIS相关函数的支持，由于MySQL的GIS支持并不完善，所以该索引方式在MySQL中很少有人使用。

5 存储引擎支持索引类型

• InnoDB 支持事务，支持行级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；
• MyISAM 不支持事务，支持表级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；
• Memory 不支持事务，支持表级别锁定，支持 B-tree、Hash 等索引，不支持 Full-text 索引；
• NDB 支持事务，支持行级别锁定，支持 Hash 索引，不支持 B-tree、Full-text 等索引；
• Archive 不支持事务，支持表级别锁定，不支持 B-tree、Hash、Full-text 等索引；

最后贴一些官方文档给出的相关表格