写在前面

从本篇开始就正式进入到MySQL的索引学习，索引非常重要，也是后续学习MySQL优化的基础。

本文主要的学习内容如下：（1）索引定义；（2）磁盘中数据的存取；（3）MySQL中的页；（4）数据检索过程；（5）数据检索过程；（6）常用数据结构；（7）文章总结。

索引

索引定义

索引是依靠某些数据结构和算法来组织数据，最终引导用户快速检索出所需要的数据。

可以看到索引有两个特点：（1）通过数据结构和算法来对原始的数据进行一些有效的组织；（2）通过有效的组织，可以引导用户快速检索出所需要的数据。

其实也就是说索引的本质，是通过不断缩小想获取数据的范围来筛选出最终想要的结果，同时将随机事件变成顺序事件，即使用索引使得我们总能使用同一种查找方式来锁定数据。

磁盘中数据的存取

由于数据最终是存储在磁盘内，因此这里以机械键盘为例，来学习磁盘中的几个概念。

（1）扇区。磁盘存储的最小单位，扇区一般大小为512Byte；
（2）磁盘块。文件系统与磁盘交互的的最小单位（计算机系统读写磁盘的最小单位），一个磁盘块由连续几个（2^n）扇区组成，块一般大小一般为4KB；
（3）磁盘读取数据。磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分。

寻道时间：指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；

旋转延迟：即磁盘转速，如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；

传输时间：指从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但是要知道一台500-MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次都需要9毫秒的时间，这显然是个灾难。

MySQL中的页

MySQL中和磁盘交互的最小单位称为页，页是MySQL内部定义的一种数据结构，默认为16kb，相当于4个磁盘块，也就是说MySQL每次从磁盘中读取一次数据是16KB，要么不读取，要读取就是16KB，注意这个值可以修改。

数据检索过程

假设我们对数据存储方式不做任何优化，直接将数据库中表的记录存储在磁盘中。现在这里有一个表，这个表中只有一个字段，类型是int，一个int类型占用4个字节(Byte)；每个磁盘块可以存储1000条记录，那么1000万条记录则需要10000个磁盘块。如果我们需要从这个1000万条记录中检索出所需要的记录，那么就需要读取10000个磁盘块，也就是需要10000次IO操作，而前面也说每次IO操作大概需要花费9ms，那么10000次的IO操作就需要花费10000*9ms=90s，也就是说1000万条记录随便查询一个就需要90s，一分半钟时间，这肯定是无法接受的，速度太慢了，因此不做任何优化是不可能。

需求

通过前面的学习，我们需要什么样的数据结构和算法呢？

对于数据结构来说，由于我们需要从磁盘中检索数据，因此希望可以减少磁盘的IO次数，最好是降低到一个稳定的常量；

对算法来说，当从磁盘中读取磁盘块的数据之后，这些块中可能包含多条记录，这些记录会被加载到内存中，那么就希望有一种算法能够快速从内存中的多条记录中快速检索出目标数据。

因此接下来就来学习一些常用的检索和算法数据结构，看看它们的特点及使用场合。

常用检索算法和数据结构

常用检索算法

循环遍历查找

从一组无序的数据中查找目标数据，常见的方法是遍历查询。n条数据，时间复杂度为O(n)，最快需要1次，最槽糕的情况需要n次，这种算法查询效率非常不稳定。

二分查找

二分查找适用于在一个有序数组中快速找到需要查找的数据。

二分查找原理：第一步，将一组无序的数据排序（升序或者降序）后放在数组中，这里以升序为例进行介绍；第二步，用数组中间位置的数据A与需要查找的数据B进行对比，如果A=B，则查找结束；如果A<B，那么将查询的范围缩小至数组中A数据右边的部分；如果A>B，那么将查询的范围缩小至数组中A数据左边的部分；之后继续执行上述操作，直至找到B数据为止。

二分查找示例：举个例子，从[1,2,3,4,5,6,7,8,9]这一有序数组中查找数字9，查找过程如下所示：
第一次查找：[1,2,3,4,5,6,7,8,9]中间位置为5，由于5<9，因此查询范围缩小至5右边的部分[6,7,8,9]；
第二次查找：[6,7,8,9]中间值为8，由于8<9，因此查询范围缩小至8右边的部分[9]；
第三次查找：直接在[9]中就能找到数字9，查找结束。

可以看到二分查找的速度是非常快的，每次查找都会使后续待查询的范围缩小一半。以上面的例子为例，如果使用循环遍历查询，那么最快需要1次，最慢需要9次，而二分法查询最快需要1次，最慢需要3次，而且耗费时间非常稳定。

二分查询法的时间复杂度是O(logN)，其中N为数据量，那么之前1000万的数据查询最多需要24次，因为2^24>1000万。

也就是说二分法查找速度非常快，但前提是目标数组有序。

常用数据结构

说完了常用的查询算法，接下来再来看看常用的数据结构。

有序数组

如果我们将MySQL中表的数据都以有序数组的方式存储在磁盘中，那么我们后续查找数据就可以按照如下步骤进行：
（1）取出目标表中的所有数据，将其存放在一个有序数组中；（2）采用二分法查找从内存中查找所需数据。

但是很明显这两个步骤都是有问题的，第一个是取出所有数据时需要耗费的IO次数较多；第二个是耗费的内存空间太大，极易造成内存崩溃。更重要的是，当在查询的时候还涉及到新增数据操作，那么为了保证数组始终处于有序状态，数组内部必然会有数据移动，这也是比较耗时的操作，因此使用有序数组来存储数据是不可取的。

链表

链表相当于在每个节点上增加一些指针，可以和前面或者后面的节点连接起来，就像一列火车，每节车厢相当于一个节点，车厢内部可以存储数据，每个车厢和下一节车厢相连。链表分为单向链表和双向链表。

单向链表是指每个节点中都有一个指向下一个节点的指针，它只能往一个方向遍历链表，结构如下：

//单向链表
class Node1{
  private Object data; //存储数据
  private Node1 nextNode; //指向下一个节点的指针
}

双向链表是指每个节点中都有两个指针，分别指向当前节点的上一个节点和下一个节点，它可以往两个方向遍历链表，结构如下：

//双向链表
class Node2{
  private Object data; //存储数据
  private Node1 prevNode; //指向上一个节点的指针
  private Node1 nextNode; //指向下一个节点的指针
}

从上面的结果就可以知道，链表存在以下优点：（1）可以根据当前节点快速定位到上一个或者下一个节点；（2）可以快速增加和删除数据，只需通过修改指针的指向就能实现链表快速增加和删除数据。

但是链表也存在以下缺点：（1）无法和数组那样，支持随机访问，数组可以通过下标来访问数据；（2）查找数据时，需要从第一个节点开始遍历，因此非常不利于数据的查找，最好的情况是1次，最槽糕的则是全遍历，一因此时间不太稳定。

二叉查找树

二叉树也称为二分树，它是每个节点最多有两个子树的树结构，通常左右子树被称为左子树和右子树。二叉树通常被用于实现二叉查找树和二叉堆。

二叉树具有如下特点：
（1）每个结点都包含一个元素以及n个子树，这里0≤n≤2；
（2）左子树和右子树有顺序，且左子树的值要小于父结点，右子树的值要大于父结点。

举个例子，数组[20,10,5,15,30,25,35]使用二叉查找树存储如下：

每个节点上面有两个指针（left,rigth），可以通过这2个指针快速访问左右子节点，检索任意一个数据最多只需要访问3个节点，相当于访问了3次数据，时间为O(logN)，和二分法查找效率一样，查询速度还是比较快的。

还是上面的数据，如果我们插入时进行了排序，此时数据是有序的，如[5,10,15,20,30,25,35]，那么就变成如下所示的结构：

可以看到此时的二叉树就退化为了一个链表，查询的最坏情况就是O(N)，N为数据量。

二叉树的缺点如下所示：
（1）查询效率不稳定，当树的左右较为平衡时，那么最差的情况为O(logN)；如果插入的数据是有序的，那么此时就退化为链表，此时查询的最坏情况就是O(N)，N为数据量；
（2）在数据量大的情况下，它会导致树的高度变高；如果每个节点对应磁盘的一个块来存储一条数据，那么磁盘的IO次数就会大幅增加，此时使用二叉树来存储数据是不明智的。

平衡二叉树（AVL树）

平衡二叉树是一种特殊的二叉树，因此它肯定满足二分树中的两个特点，同时它还有一个特点：左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树相对于二叉树而言，树的左右比较平衡，不会出现二叉树退化成链表的情况。无论怎么插入数据，最终通过一些调整，都能够保证树左右高度相差不大于1。这样使得查询速度比较稳定，查询中遍历节点控制在O(logN)范围内。

如果数据都存储在内存中，采用AVL树来存储这是可以的，查询效率非常高。但是数据肯定是存储在磁盘中，采用这种结构的话，每个节点对应一个磁盘块，数据量大的时候，也会和二叉树一样，导致树的高度变高，会增加磁盘的IO次数，因此使用这种结构来存储数据也是不明智的。

其实除了上面介绍的数据结构外，还有B-树、B+树，由于这两个结构较为重要，因此会在下一篇文章中进行介绍。

文章总结

本篇主要学习了MySQL中的索引，页和数据检索过程，之后介绍了常用的数据检索算法和数据结构。