MySQL数据库，详解索引原理(一)

索引的本质：通过不断地缩⼩想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是⽤同⼀种查找⽅式来锁定数据。磁盘中数据的存取

以机械硬盘来说，先了解⼏个概念。

扇区：磁盘存储的最⼩单位，扇区⼀般⼤⼩为512Byte。

磁盘块：⽂件系统与磁盘交互的的最⼩单位（计算机系统读写磁盘的最⼩单位），⼀个磁盘块由连续⼏个（ ）扇区组成，块⼀般⼤⼩⼀般为4KB。

磁盘读取数据：磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘⼀般在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条记录，100万的记录需要1000个磁盘块，如果我们需要从这100万记录中检索所需要的记录，需要读取1000个磁盘块的数据（需要1000次io），每次io需要9ms，那么1000次需要

9000ms=9s，100条数据随便⼀个查询就是9秒，这种情况我们是⽆法接受的，显然是不⾏的。

2n我们迫切的需求是什么？

我们迫切需要这样的数据结构和算法：

1. 需要⼀种数据存储结构：当从磁盘中检索数据的时候能，够减少磁盘的io次数，最好能够降低到⼀个稳定的常量值

2. 需要⼀种检索算法：当从磁盘中读取磁盘块的数据之后，这些块中可能包含多条记录，这些记录被加载到内存中，那么需要⼀种算法能够快速从内存多条记录中快速检索出⽬标数据

我们来找找，看是否能够找到这样的算法和数据结构。

我们看⼀下常见的检索算法和数据结构。

循环遍历查找

从⼀组⽆序的数据中查找⽬标数据，常见的⽅法是遍历查询，n条数据，时间复杂度为O(n)，最快需要1次，最坏的情况需要n次，查询效率不稳定。

⼆分法查找

⼆分法查找也称为折半查找，⽤于在⼀个有序数组中快速定义某⼀个需要查找的数据。

原理是：

先将⼀组⽆序的数据排序（升序或者降序）之后放在数组中，此处⽤升序来举例说明：⽤数组中间位置的数据A和需要查找的数据F对⽐，如果A=F，则结束查找；如果A<F，则将

查找的范围缩⼩⾄数组中A数据右边的部分；如果A>F，则将查找范围缩⼩⾄数组中A数据左边的部分，继续按照上⾯的⽅法直到找到F为⽌。

⽰例：从下列有序数字中查找数字9，过程如下

[1,2,3,4,5,6,7,8,9]

第1次查找：[1,2,3,4,5,6,7,8,9]中间位置值为5，9>5，将查找范围缩⼩⾄5右边的部分：

[6、7、8、9]

第2次查找：[6、7、8、9]中间值为8，9>8 ，将范围缩⼩⾄8右边部分：[9]

第3次查找：在[9]中查找9，找到了。

可以看到查找速度是相当快的，每次查找都会使范围减半，如果我们采⽤顺序查找，上⾯数据最快需要1次，最多需要9次，⽽⼆分法查找最多只需要3次，耗时时间也⽐较稳定。

⼆分法查找时间复杂度是:O(logN)(N为数据量)，100万数据查找最多只需要20次（=1048576）

⼆分法查找数据的优点：定位数据⾮常快，前提是：⽬标数组是有序的。