索引分几种？

前言

年前特地买了一台笔记本，结果过年没打开过两次，读书时代带书回也没翻过，这么多年依旧如此。

新的一年祝大家牛年大吉，越来越牛。

今儿来简单说一下索引相关的知识点。

索引

是存储引擎用于快速找到记录的一种数据结构。

就相当于是书的目录，查找数据就是根据目录找内容。

存储引擎先在索引中找到对应的值，然后根据匹配到的索引记录找到对应的数据行。

索引可以包含一个或多个列，如果是多个列，那么列的顺序很重要，MySQL只能高效的使用索引的最左前缀列。

优点

1、极大减少服务器需扫描的数据量

2、可帮助服务器避免排序和临时表

3、可将随机IO变成顺序IO

索引类型

（1）B-Tree

平衡多路查找树

「一棵m阶的B-Tree特性如下：」

1、每个节点最多有m个子节点

2、除了根节点和叶子节点外，其他每个节点至少有Ceil(m/2)个子节点

3、若根节点不是叶子节点，则至少有2个子节点

4、所有叶子节点都在同一层，且不包含其他关键字信息

5、每个非叶子节点包含n个关键字信息（P0,P1,...,Pn,K1,K2,...Kn）

6、关键字的个数n满足：ceil(m/2)-1<=n<=m-1

7、Ki(i=1,..,n)为关键字，且关键字升序排序

8、Pi(i=1,..,n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于Ki，但都大于K(i-1)

B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为20和49，P1指针指向的子树的数据范围为小于20，P2指针指向的子树的数据范围为20~49，P3指针指向的子树的数据范围为大于49。

模拟查找关键字29的过程：

1. 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2. 比较关键字29在区间（20,49），找到磁盘块1的指针P2。
3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4. 比较关键字29在区间（23,35），找到磁盘块3的指针P2。
5. 根据P2指针找到磁盘块9，读入内存。【磁盘I/O操作第3次】
6. 在磁盘块8中的关键字列表中找到关键字29。

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

（2）B+Tree

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

从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同：

1. 非叶子节点只存储键值信息。
2. 所有叶子节点之间都有一个链指针。
3. 数据记录都存放在叶子节点中。

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

可能上面例子中只有11条数据记录，看不出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亿 条记录。

（3）哈希索引

基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

如果某个哈希索引包含A、B列，那么只查询条件只有A列，索引是不生效的。

哈希索引不支持范围查询。只支持等值查询。

（4）空间数据索引

MyISAM表支持空间索引，可以用作地理数据存储。空间索引会从所有维度来索引数据

（5）全文索引

全文索引更类似于搜索引擎做的事情，而不是简单的Where条件匹配。