MySQL的索引（一）

索引的出现就是为了提高数据查询效率，就像字典里的目录一样。当我们需要查找某个字或者某个单词的时候肯定会先进入目录页，查找相应的页数，这就是索引。

索引模型有很多种，主要的就是这三种：哈希表、有序数组、搜索树。

它是一种key-value型的数据结构，我们只要输入要查找的key值就可以找到与它对应的Value了，它的思路就是经过hash函数将key换算到一个确定的位置，然后把value放在数组的这个位置。

但是可能会出现这个问题：多个值经过Hash函数换算，有可能会换算到一个位置，所以为了解决这种情况，就有一种方法是拉链法。拉链法就是在这个节点上拉出一条链表。

因为增加的数据并不是按顺序递增的，所以它增加数据的时候比较快，只需要往后面增加就可以了。但是也是因为这样，它查找效率比较低下。如果我要查找一个区间，那么就得需要去遍历整个哈希表，这种查询速度是非常让人绝望的。

所以Hash表这种结构就适用于等值查询的场景，比如现在常见的Redis、Memcached等一些NOSQL型的数据库。

上面说了Hash表在范围查找的场景中速度令人绝望，作为改进有了有序数组，它在范围查找和等值查找的性能都是比较优秀的。

有序数组，见名知意，它就是有排列顺序的数组。如果我们要查找身份证的话，假定身份证号没有重复(因为实际上，身份证号是有可能重复的)，让这个数组按递增序列来保存。我们如果要查找一个身份证，只需要通过二分查找就可以找到了，它的时间复杂度就是O(log(N))。如果我要范围查找的话，也可以用二分查找来找。

如果我们只看查找速度的话，有序数组这个数据结构就是一个非常棒的存储结构，但是我们在插入或者删除一条记录的时候，我们得要挪动后面所有的记录，这样它的成本太高，速度太慢。

所以，有序数组一般可以做静态存储引擎。这种引擎保存的就是那种不会再被修改的数据。

我们也可以用二叉搜索树来做存储结构，它的特点就是每个节点的左节点小于父节点，父节点又小于右儿子。它的平均时间复杂度是O(log(N))，为了维持这个时间复杂度，所以它要求这颗二叉搜索树必须为平衡二叉树。

树可以有二叉也可以由多叉，不过相对来说二叉树是搜索效率最高的。你可以去看看数据库的存储引擎，大多数的存储并不是用的二叉树。虽然二叉树的查询效率高，但是索引不仅仅在内存中，还要写到磁盘上。

一棵100万节点的平衡二叉树，树高20，一次查询可能就要需要访问20个数据块。在机械硬盘的时代，从磁盘随机读取一个数据块差不多需要用10ms的时间，如果我要单独访问一行数据，可能就要20*10ms的时间，这个速度是真的慢！

作为主流的数据库引擎，它的表是根据主键顺序以索引的形式存放的，这个表被称为索引组织表。InnoDB的索引模型是B+树，它的所有数据都存放在B+树里的。

主键索引的叶子结点存储的是正行数据。在InnoDB里，主键索引被称为聚簇索引。

非主键索引的叶子结点存的是主键的值。在InnoDB里，非主键索引被称为二级索引。

问题来了：这两种索引查询有什么区别？

如果是主键查询方式，我只需要搜索主键这棵B+树就可以了。

如果是非主键查询方式，也就是我们普通的查询方式，我们先搜索非主键的索引树，找到它的主键，再通过主键去主键的索引树查找。这也就是为什么非主键索引被称为二级索引的原因。这个过程被称为回表。

所以我们一般使用的时候就尽量使用主键查询。