常见索引类型及在MySQL中的应用

什么是索引？

索引是一种数据结构，是对记录集的一个或多个字段的值进行排序的存储结构。

索引是如何工作的？

索引的出现其实是为了提高数据查询的效率，就像书的目录一样，根据目录可以快速定位到内容，类比于索引，根据索引提供指向存储在表的指定列中的数据值的指针，根据指针找到包含该值的行。

索引的常见模型

• 哈希表
• 有序数组
• B+树

哈希表

哈希表模型是将待查询的值放入key中，value值放入数组中，

当使用哈希表时，key值计算成确定位置，将value值放入该地址对应的哈希槽，取值通过key值去对应哈希槽取数据，但经过哈希后的key可能会出现数据重复一致（哈希冲突）的情况，此时哈希槽中的值是一个列表，使用列表遍历查询到目标值。

Usern2、Usern4计算出的哈希值都是N，N对应的User4、User2，通过遍历取出数据。

当Key值不是递增的时，此情况下新增数据速度快，但缺点是数据不是有序的，在区间查询时需要遍历实现，所以速度很慢。

因此哈希表模型只适用于等值查询的场景。比如 Memcached 及其他一些 NoSQL 引擎。

等值查询：确定的条件查询，即可以使用等号的查询

与之对应的是模糊查询、范围查询。

有序数组

有序数组在等值查询和范围查询场景中的性能都非常优秀。

仅看查询效率，有序数组是最好的数据结构，使用二分法查询可以快速查询到目标值，时间复杂度是O(log(N))。但是在中间插入一个记录时就必须得挪动后面所有的记录，成本太高。

有序数组只适用于静态存储引擎。

二叉树

二叉树的特点是：父节点左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值。查询复杂度是O(log(N))。

O(log(N))：使用二分法查询，最理想的情况是查询一次即可，最坏的情况下需要查询的次数。

16个元素的有序数组，使用二分法查找其中一个元素，最多需要查询log 2 16 = 4次。

二叉树是搜索效率最高的，但是实际上没有多少数据库存储使用，因为索引不止存在于内存中，还要写在磁盘上。数据量较大时，二叉树的树过高，查询时需要访问过多节点，即需要硬盘多次寻址，这是一个耗时操作。

N叉树

概念：允许树的每个节点可以有两个以上的子节点，那么这个树就称为N阶多叉树。

MySQL默认一个节点的长度为16K，一个整数(bigint)字段索引的长度为8B，另外每个索引还跟着6B的指向其子树的指针；所以16K/14B≈1170。

树高是4的时候，就可以存1200的3次方个值（17亿），树根的数据总是存在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。树的第二层也大概率在内存中，那么访问磁盘的次数就少了。

N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中。