本文主要是介绍【MySQL进阶之路】为什么索引能快速的在海量数据中查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
引言
认识磁盘
磁盘的寻址
磁盘的抽象化理解
系统IO交互的基本单位
MySQL 与磁盘交互基本单位
理解Page方案
数据结构组织数据
单个page
多个page
大量数据
不同的数据类型
为什么不采用其他数据结构
B树和B+树的区别
聚簇索引 VS 非聚簇索引
🤗个人主页：东洛的克莱斯韦克-CSDN博客
| 基础 | 约束 | 查询示例 |
| MySQL基础 | MySQL约束 | 多表查询 |
引言
索引：提高数据库的性能，索引是物美价廉的东西了。不用加内存，不用改程序，不用调sql，只要执行 正确的 create index ，查询速度就可能提高成百上千倍。但是天下没有免费的午餐，查询速度的提高 是以插入、更新、删除的速度为代价的，这些写操作，增加了大量的IO。所以它的价值，在于提高一个 海量数据的检索速度。
本文探讨索引怎么做到海量数据的快速查找。
首先要谈IO问题，数据是在磁盘中的，如果要对数据进行增删查改工作，就必须把磁盘的数据加载到内存，操作系统就要和外设交互。而IO是很慢的一种行为，要实现快速查询，MySQL的索引首先要解决的就是IO次数的问题。
接下来会再谈数据结构和算法的问题，既然数据从磁盘加载到内存了，直觉告诉我们，这些数据必然不是杂乱无章的放在内存中的，不然不可能快速查询，那么这种数据结构又是什么呢
综上，本文会从IO和数据结构两个方面阐述索引为什么可以在海量数据中进行快速查找。
认识磁盘
要理解IO会什么会很慢就要了解一下磁盘，一个很简单的结论就是：磁盘是机器设备，磁盘存取数据时要做机器运动，这种运动不论在技术上怎么优化，和光电信号比起来慢了很多级别。
而操作系统会想尽一切办法减少磁盘机器运动的次数——在相同的数据量下，尽量做到磁盘机器运动次数最少。
磁盘的重要的两个结构是盘片和磁头，盘片上有磁性物质，可以记录而进程数据。磁头用来对二进制数据做存取。
盘面上可以划分为多个磁道，每个磁道又可以划分为多个扇区，，扇区是硬盘的最小的存储单元，一般是存储512字节（byte）
磁盘不仅是外设，而且还是机器设备。相同数据量下磁头移动的次数越少磁盘的效率越高。
磁盘的寻址
对磁盘上的数据做存取，首先要定位哪个盘面，然后定位哪个磁道，然后在定位哪个扇区，通过确定盘面，磁道，扇区来定位磁盘上的数据，这种寻址方式称为CHS寻址。
磁盘的抽象化理解
如果把所有磁道展开成一条直线，每个扇面在这条直线上均匀分布。像数组一般，每个扇面都有唯一的编号。这种编号的方式称为 LBA寻址
LBA地址=（柱面编号×硬盘磁头的总数+磁头编号）×扇区数+扇区编号-1
扇区数为每磁道的扇区数
系统IO交互的基本单位
我们现在已经能够在硬件层面定位，任何一个基本数据块了(扇区)。那么在系统软件上，就直接按照扇区 (512字节，部分4096字节),进行IO交互吗？
不是 如果操作系统直接使用硬件提供的数据大小进行交互，那么系统的IO代码，就和硬件强相关，换言之，如果硬件发生变化，系统必须跟着变化。
从目前来看，单次IO 512字节，还是太小了。IO单位小，意味着读取同样的数据内容，需要进行多 次磁盘访问，会带来效率的降低。
在Linux文件系统，就是在磁盘的基本结构下建立的，文件系统读取基本单位就不是扇区，而是数据块。 系统读取磁盘，是以块为单位的，基本单位是 4KB 。
在Linux系统中，不管是单次IO的数据大小，还是内存管理模块中基本内存单元的大小都是4KB。
MySQL 与磁盘交互基本单位
而 MySQL 作为一款应用软件，可以想象成一种特殊的文件系统。它有着更高的IO场景，所以，为了提高 基本的IO效率， MySQL 进行IO的基本单位是 16KB
也就是说，磁盘这个硬件设备的基本单位是 512 字节，而 MySQL InnoDB引擎 使用 16KB 进行IO交互。 即， MySQL 和磁盘进行数据交互的基本单位是 16KB 。这个基本数据单元，在 MySQL 这里叫做page
MySQL是上层应用，在逻辑上虽然是以16KB为单位在和磁盘进行IO交互，但真正和硬件打交道的只能是操作系统，也就是说，MySQL服务要进行一次IO行为，操作系统最多要4次IO才能拿到数据，并把数据交给上层MySQL服务。
MySQL服务是用C/C++写的，所谓的用户层缓冲区可以理解为MySQL这个进程自己new的一块空间。
理解Page方案
即使我们要查10个字节的数据，MySQL服务也会以16KB为大小把数据加载到MySQL缓冲区中的一个page中。
为何MySQL和磁盘进行IO交互的时候，要采用Page的方案进行交互呢?用多少，加载多少不香吗?
要插入5条记录，如果MySQL要查找id=2的记录，第一次加载id=1，第二次加载id=2，一次一条记录，那 么就需要2次IO。如果要找id=5，那么就需要5次IO。 但，如果这5条(或者更多)都被保存在一个Page中(16KB，能保存很多记录),那么第一次IO查找id=2的时 候，整个Page会被加载到MySQL的Buffer Pool中，这里完成了一次IO。但是往后如果在查找id=1,3,4,5 等，完全不需要进行IO了，而是直接在内存中进行了。
所以，就在单Page里面，大大减少了IO的次数。
那怎么保证用户一定下次找的数据，就在这个Page里面？当然不能严格保证，但是有很大概率，因为有局部性原理。 往往IO效率低下的最主要矛盾不是IO单次数据量的大小，而是IO的次数。
数据结构组织数据
单个page
MySQL 中要管理很多数据表文件，而要管理好这些文件，就需要 先描述，在组织 ,我们目前可以简单理解 成一个个独立文件是有一个或者多个Page构成的。
不同的 Page ，在 MySQL 中，都是 16KB ，使用 prev 和 next 构成双向链表 因为有主键的问题， MySQL 会默认按照主键给我们的数据进行排序，从上面的Page内数据记录可以看 出，数据是有序且彼此关联的。
多个page
通过上面的分析，我们知道，上面页模式中，只有一个功能，就是在查询某条数据的时候直接将一 整页的数据加载到内存中，以减少硬盘IO次数，从而提高性能。但是，我们也可以看到，现在的页 模式内部，实际上是采用了链表的结构，前一条数据指向后一条数据，本质上还是通过数据的逐条 比较来取出特定的数据。 如果有1千万条数据，一定需要多个Page来保存1千万条数据，多个Page彼此使用双链表链接起 来，而且每个Page内部的数据也是基于链表的。那么，查找特定一条记录，也一定是线性查找。这 效率也太低了。
所以，在一个page中不仅存数据，还存一个类似于目录的东西，通过主键值，或唯一键值来映射数据。
关于页目录，可以用如下场景理解
我们在看《谭浩强C程序设计》这本书的时候，如果我们要看，找到该章节有两种做法 从头逐页的向后翻，直到找到目标内容 通过书提供的目录，发现指针章节在234页(假设)，那么我们便直接翻到234页。同时，查找目录的 方案，可以顺序找，不过因为目录肯定少，所以可以快速提高定位 本质上，书中的目录，是多花了纸张的，但是却提高了效率 所以，目录，是一种“空间换时间的做法”
大量数据
MySQL 中每一页的大小只有 16KB ，单个Page大小固定，所以随着数据量不断增大， 16KB 不可能存下 所有的数据，那么必定会有多个页来存储数据。
在单表数据不断被插入的情况下， MySQL 会在容量不足的时候，自动开辟新的Page来保存新的数据，然 后通过指针的方式，将所有的Page组织起来。
我们就可以通过多个Page遍历，Page内部通过目录来快速定位数据。可是，貌似这样也有效率问 题，在Page之间，也是需要 MySQL 遍历的，遍历意味着依旧需要进行大量的IO，将下一个Page加载到 内存，进行线性检测。这样就显得我们之前的Page内部的目录，有点杯水车薪了。 那么如何解决呢？解决方案，其实就是我们之前的思路，给Page也带上目录。
使用一个目录项来指向某一页，而这个目录项存放的就是将要指向的页中存放的最小数据的键值。 和页内目录不同的地方在于，这种目录管理的级别是页，而页内目录管理的级别是行。 其中，每个目录项的构成是：键值+指针。图中没有画全。
存在一个目录页来管理页目录，目录页中的数据存放的就是指向的那一页中最小的数据。有数据，就可 通过比较，找到该访问那个Page，进而通过指针，找到下一个Page。
其实目录页的本质也是页，普通页中存的数据是用户数据，而目录页中存的数据是普通页的地址。 可是，我们每次检索数据的时候，该从哪里开始呢？虽然顶层的目录页少了，但是还要遍历啊？不用担 心，可以在加目录页
这货就是传说中的B+树啊！没错，至此，我们已经给我们的表user构建完了主键索引。
Page分为目录页和数据页。目录页只放各个下级Page的最小键值。 查找的时候，自定向下找，只需要加载部分目录页到内存，即可完成算法的整个查找过程，大大减 少了IO次数
在MySQL服务的缓冲区中，内存的基本单元是一个page，也就是16KB大小。然后根据主键或唯一键用B+树把数据组织起来。
不同的数据类型
如下是不同的存储引擎所采用的数据结构
| 存储引擎 | 索引数据结构 |
|---|---|
| InnoDB | BTREE |
| MyISAM | BTREE |
| MEMORY/HEAP | HASH, BTREE |
| NDB | HASH, BTREE |
为什么不采用其他数据结构
链表：线性遍历
二叉搜索树：退化问题，可能退化成为线性结构
AVL &&红黑树：虽然是平衡或者近似平衡，但是毕竟是二叉结构，相比较多阶B+，意味着树整体 过高，大家都是自顶向下找，层高越低，意味着系统与硬盘更少的IO Page交互。虽然你很秀，但 是有更秀的。
Hash：官方的索引实现方式中， MySQL 是支持HASH的，不过 InnoDB 和 MyISAM 并不支持.Hash跟 进其算法特征，决定了虽然有时候也很快(O(1))，不过，在面对范围查找就明显不行
B树和B+树的区别
B树节点，既有数据，又有Page指针，而B+，只有叶子节点有数据，其他目录页，只有键值和 Page指针 B+叶子节点，全部相连，而B没有
节点不存储data，这样一个节点就可以存储更多的key。可以使得树更矮，所以IO操作次数更少。 叶子节点相连，更便于进行范围查找
传送门：数据结构可视化
聚簇索引 VS 非聚簇索引
MyISAM 存储引擎-主键索引 MyISAM 引擎同样使用B+树作为索引结果，叶节点的data域存放的是数据记录的地址。下图为 MyISAM 表的主索引， Col1 为主键。
其中， MyISAM 最大的特点是，将索引Page和数据Page分离，也就是叶子节点没有数据，只有对应数据 的地址。 相较于 InnoDB 索引， InnoDB 是将索引和数据放在一起的。其中， MyISAM 这种用户数据与索引数据分离的索引方案，叫做非聚簇索引，InnoDB 这种用户数据与索引数据在一起索引方案，叫做聚簇索引
当然， MySQL 除了默认会建立主键索引外，我们用户也有可能建立按照其他列信息建立的索引，一般这 种索引可以叫做辅助（普通）索引。 对于 MyISAM ,建立辅助（普通）索引和主键索引没有差别，无非就是主键不能重复，而非主键可重复。 下图就是基于 MyISAM 的 Col2 建立的索引，和主键索引没有差别
， InnoDB 除了主键索引，用户也会建立辅助（普通）索引，我们以上表中的 Col3 建立对应的辅助 索引如下图：
可以看到， InnoDB 的非主键索引中叶子节点并没有数据，而只有对应记录的key值。 所以通过辅助（普通）索引，找到目标记录，需要两遍索引：首先检索辅助索引获得主键，然后用主键 到主索引中检索获得记录。这种过程，就叫做回表查询 为何 InnoDB 针对这种辅助（普通）索引的场景，不给叶子节点也附上数据呢？原因就是太浪费空间 了。
这篇关于【MySQL进阶之路】为什么索引能快速的在海量数据中查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
