MySQL 系列的目标是: 通过这个系列从入门到全面掌握一个高级开发所需要的全部技能.
欢迎大家加我微信 itsoku 一起交流 java, 算法, 数据库相关技术.
这是 MySQL 系列第 22 篇.
背景
使用 MySQL 最多的就是查询, 我们迫切的希望 MySQL 能查询的更快一些, 我们经常用到的查询有:
按照 id 查询唯一一条记录
按照某些个字段查询对应的记录
查找某个范围的所有记录(between and)
对查询出来的结果排序
MySQL 的索引的目的是使上面的各种查询能够更快.
预备知识
什么是索引?
上一篇中有详细的介绍, 可以过去看一下: 什么是索引?
索引的本质: 通过不断地缩小想要获取数据的范围来筛选出最终想要的结果, 同时把随机的事件变成顺序的事件, 也就是说, 有了这种索引机制, 我们可以总是用同一种查找方式来锁定数据.
磁盘中数据的存取
以机械硬盘来说, 先了解几个概念.
扇区: 磁盘存储的最小单位, 扇区一般大小为 512Byte.
磁盘块: 文件系统与磁盘交互的的最小单位 (计算机系统读写磁盘的最小单位), 一个磁盘块由连续几个(2^n) 扇区组成, 块一般大小一般为 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 秒, 这种情况我们是无法接受的, 显然是不行的.
我们迫切的需求是什么?
我们迫切需要这样的数据结构和算法:
需要一种数据存储结构: 当从磁盘中检索数据的时候能, 够减少磁盘的 io 次数, 最好能够降低到一个稳定的常量值
需要一种检索算法: 当从磁盘中读取磁盘块的数据之后, 这些块中可能包含多条记录, 这些记录被加载到内存中, 那么需要一种算法能够快速从内存多条记录中快速检索出目标数据
我们来找找, 看是否能够找到这样的算法和数据结构.
我们看一下常见的检索算法和数据结构.
循环遍历查找
从一组无序的数据中查找目标数据, 常见的方法是遍历查询, 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 次(2^20=1048576)
二分法查找数据的优点: 定位数据非常快, 前提是: 目标数组是有序的.
有序数组
如果我们将 MySQL 中表的数据以有序数组的方式存储在磁盘中, 那么我们定位数据步骤是:
取出目标表的所有数据, 存放在一个有序数组中
如果目标表的数据量非常大, 从磁盘中加载到内存中需要的内存也非常大
步骤取出所有数据耗费的 io 次数太多, 步骤 2 耗费的内存空间太大, 还有新增数据的时候, 为了保证数组有序, 插入数据会涉及到数组内部数据的移动, 也是比较耗时的, 显然用这种方式存储数据是不可取的.
链表
链表相当于在每个节点上增加一些指针, 可以和前面或者后面的节点连接起来, 就像一列火车一样, 每节车厢相当于一个节点, 车厢内部可以存储数据, 每个车厢和下一节车厢相连.
链表分为单链表和双向链表.
单链表
每个节点中有持有指向下一个节点的指针, 只能按照一个方向遍历链表, 结构如下:
- // 单项链表
- class Node1{
- private Object data;// 存储数据
- private Node1 nextNode;// 指向下一个节点
- }
双向链表
每个节点中两个指针, 分别指向当前节点的上一个节点和下一个节点, 结构如下:
- // 双向链表
- class Node2{
- private Object data;// 存储数据
- private Node1 prevNode;// 指向上一个节点
- private Node1 nextNode;// 指向下一个节点
- }
链表的优点:
可以快速定位到上一个或者下一个节点
可以快速删除数据, 只需改变指针的指向即可, 这点比数组好
链表的缺点:
无法向数组那样, 通过下标随机访问数据
查找数据需从第一个节点开始遍历, 不利于数据的查找, 查找时间和无需数据类似, 需要全遍历, 最差时间是 O(N)
二叉查找树
二叉树是每个结点最多有两个子树的树结构, 通常子树被称作 "左子树"(left subtree)和 "右子树"(right subtree). 二叉树常被用于实现二叉查找树和二叉堆. 二叉树有如下特性:
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).
二叉树的优缺点:
查询数据的效率不稳定, 若树左右比较平衡的时, 最差情况为 O(logN), 如果插入数据是有序的, 退化为了链表, 查询时间变成了 O(N)
数据量大的情况下, 会导致树的高度变高, 如果每个节点对应磁盘的一个块来存储一条数据, 需 io 次数大幅增加, 显然用此结构来存储数据是不可取的
平衡二叉树(AVL 树)
平衡二叉树是一种特殊的二叉树, 所以他也满足前面说到的二叉查找树的两个特性, 同时还有一个特性:
它的左右两个子树的高度差的绝对值不超过 1, 并且左右两个子树都是一棵平衡二叉树.
平衡二叉树相对于二叉树来说, 树的左右比较平衡, 不会出现二叉树那样退化成链表的情况, 不管怎么插入数据, 最终通过一些调整, 都能够保证树左右高度相差不大于 1.
这样可以让查询速度比较稳定, 查询中遍历节点控制在 O(logN)范围内
如果数据都存储在内存中, 采用 AVL 树来存储, 还是可以的, 查询效率非常高. 不过我们的数据是存在磁盘中, 用过采用这种结构, 每个节点对应一个磁盘块, 数据量大的时候, 也会和二叉树一样, 会导致树的高度变高, 增加了 io 次数, 显然用这种结构存储数据也是不可取的.
B - 树
B 杠树, 千万不要读作 B 减树了, B - 树在是平衡二叉树上进化来的, 前面介绍的几种树, 每个节点上面只有一个元素, 而 B - 树节点中可以放多个元素, 主要是为了降低树的高度.
一棵 m 阶的 B-Tree 有如下特性[特征描述的有点绕, 看不懂的可以跳过, 看后面的图] :
每个节点最多有 m 个孩子, m 称为 b 树的阶
除了根节点和叶子节点外, 其它每个节点至少有 Ceil(m/2)个孩子
若根节点不是叶子节点, 则至少有 2 个孩子
所有叶子节点都在同一层, 且不包含其它关键字信息
每个非终端节点包含 n 个关键字 (健值) 信息
关键字的个数 n 满足: ceil(m/2)-1 <= n <= m-1
ki(i=1,...n)为关键字, 且关键字升序排序
Pi(i=1,...n)为指向子树根节点的指针. P(i-1)指向的子树的所有节点关键字均小于 ki, 但都大于 k(i-1)
B-Tree 结构的数据可以让系统高效的找到数据所在的磁盘块. 为了描述 B-Tree, 首先定义一条记录为一个二元组[key, data] ,key 为记录的键值, 对应表中的主键值, data 为一行记录中除主键外的数据. 对于不同的记录, key 值互不相同.
B-Tree 中的每个节点根据实际情况可以包含大量的关键字信息和分支, 如下图所示为一个 3 阶的 B-Tree:
每个节点占用一个盘块的磁盘空间, 一个节点上有两个升序排序的关键字和三个指向子树根节点的指针, 指针存储的是子节点所在磁盘块的地址. 两个键将数据划分成的三个范围域, 对应三个指针指向的子树的数据的范围域. 以根节点为例, 关键字为 17 和 35,P1 指针指向的子树的数据范围为小于 17,P2 指针指向的子树的数据范围为 17~35,P3 指针指向的子树的数据范围为大于 35.
模拟查找关键字 29 的过程:
根据根节点找到磁盘块 1, 读入内存.[磁盘 I/O 操作第 1 次]
比较关键字 29 在区间(17,35), 找到磁盘块 1 的指针 P2
根据 P2 指针找到磁盘块 3, 读入内存.[磁盘 I/O 操作第 2 次]
比较关键字 29 在区间(26,30), 找到磁盘块 3 的指针 P2
根据 P2 指针找到磁盘块 8, 读入内存.[磁盘 I/O 操作第 3 次]
在磁盘块 8 中的关键字列表中找到关键字 29
分析上面过程, 发现需要 3 次磁盘 I/O 操作, 和 3 次内存查找操作, 由于内存中的关键字是一个有序表结构, 可以利用二分法快速定位到目标数据, 而 3 次磁盘 I/O 操作是影响整个 B-Tree 查找效率的决定因素.
B - 树相对于 avl 树, 通过在节点中增加节点内部数据的个数来减少磁盘的 io 操作.
上面我们说过 MySQL 是采用页方式来读写数据, 每页是 16KB, 我们用 B - 树来存储 MySQL 的记录, 每个节点对应 MySQL 中的一页 (16KB), 假如每行记录加上树节点中的 1 个指针占 160Byte, 那么每个节点可以存储 1000(16KB/160byte) 条数据, 树的高度为 3 的节点大概可以存储(第一层 1000 + 第二层 1000^2 + 第三层 1000^3)10 亿条记录, 是不是非常惊讶, 一个高度为 3 个 B - 树大概可以存储 10 亿条记录, 我们从 10 亿记录中查找数据只需要 3 次 io 操作可以定位到目标数据所在的页, 而页内部的数据又是有序的, 然后将其加载到内存中用二分法查找, 是非常快的.
可以看出使用 B - 树定位某个值还是很快的 (10 亿数据中 3 次 io 操作 + 内存中二分法), 但是也是有缺点的: B - 不利于范围查找, 比如上图中我们需要查找[15,36] 区间的数据, 需要访问 7 个磁盘块(1/2/7/3/8/4/9),io 次数又上去了, 范围查找也是我们经常用到的, 所以 b - 树也不太适合在磁盘中存储需要检索的数据.
b + 树
先看个 b + 树结构图:
b + 树的特征
每个结点至多有 m 个子女
除根结点外, 每个结点至少有 [m/2] 个子女, 根结点至少有两个子女
有 k 个子女的结点必有 k 个关键字
父节点中持有访问子节点的指针
父节点的关键字在子节点中都存在(如上面的 1/20/35 在每层都存在), 要么是最小值, 要么是最大值, 如果节点中关键字是升序的方式, 父节点的关键字是子节点的最小值
最底层的节点是叶子节点
除叶子节点之外, 其他节点不保存数据, 只保存关键字和指针
叶子节点包含了所有数据的关键字以及 data, 叶子节点之间用链表连接起来, 可以非常方便的支持范围查找
b + 树与 b - 树的几点不同
b + 树中一个节点如果有 k 个关键字, 最多可以包含 k 个子节点(k 个关键字对应 k 个指针); 而 b - 树对应 k+1 个子节点(多了一个指向子节点的指针)
b + 树除叶子节点之外其他节点值存储关键字和指向子节点的指针, 而 b - 树还存储了数据, 这样同样大小情况下, b + 树可以存储更多的关键字
b + 树叶子节点中存储了所有关键字及 data, 并且多个节点用链表连接, 从上图中看子节点中数据从左向右是有序的, 这样快速可以支撑范围查找(先定位范围的最大值和最小值, 然后子节点中依靠链表遍历范围数据)
B-Tree 和 B+Tree 该如何选择?
B-Tree 因为非叶子结点也保存具体数据, 所以在查找某个关键字的时候找到即可返回. 而 B+Tree 所有的数据都在叶子结点, 每次查找都得到叶子结点. 所以在同样高度的 B-Tree 和 B+Tree 中, B-Tree 查找某个关键字的效率更高.
由于 B+Tree 所有的数据都在叶子结点, 并且结点之间有指针连接, 在找大于某个关键字或者小于某个关键字的数据的时候, B+Tree 只需要找到该关键字然后沿着链表遍历就可以了, 而 B-Tree 还需要遍历该关键字结点的根结点去搜索.
由于 B-Tree 的每个结点 (这里的结点可以理解为一个数据页) 都存储主键 + 实际数据, 而 B+Tree 非叶子结点只存储关键字信息, 而每个页的大小有限是有限的, 所以同一页能存储的 B-Tree 的数据会比 B+Tree 存储的更少. 这样同样总量的数据, B-Tree 的深度会更大, 增大查询时的磁盘 I/O 次数, 进而影响查询效率.
MySQL 的存储引擎和索引
MySQL 内部索引是由不同的引擎实现的, 主要说一下 InnoDB 和 MyISAM 这两种引擎中的索引, 这两种引擎中的索引都是使用 b + 树的结构来存储的.
InnoDB 中的索引
Innodb 中有 2 种索引: 主键索引(聚集索引), 辅助索引(非聚集索引).
主键索引: 每个表只有一个主键索引, 叶子节点同时保存了主键的值也数据记录.
辅助索引: 叶子节点保存了索引字段的值以及主键的值.
MyISAM 引擎中的索引
不管是主键索引还是辅助索引结构都是一样的, 叶子节点保存了索引字段的值以及数据记录的地址.
如下图:
有一张表, Id 作为主索引, Name 作为辅助索引.
InnoDB 数据检索过程
如果需要查询 id=14 的数据, 只需要在左边的主键索引中检索就可以了.
如果需要搜索 name='Ellison'的数据, 需要 2 步:
先在辅助索引中检索到 name='Ellison'的数据, 获取 id 为 14
再到主键索引中检索 id 为 14 的记录
辅助索引这个查询过程在 MySQL 中叫做回表.
MyISAM 数据检索过程
在索引中找到对应的关键字, 获取关键字对应的记录的地址
通过记录的地址查找到对应的数据记录
我们用的最多的是 innodb 存储引擎, 所以此处主要说一下 innodb 索引的情况, innodb 中最好是采用主键查询, 这样只需要一次索引, 如果使用辅助索引检索, 涉及到回表操作, 比主键查询要耗时一些.
innodb 中辅助索引为什么不像 myisam 那样存储记录的地址?
表中的数据发生变更的时候, 会影响其他记录地址的变化, 如果辅助索引中记录数据的地址, 此时会受影响, 而主键的值一般是很少更新的, 当页中的记录发生地址变更的时候, 对辅助索引是没有影响的.
我们来看一下 MySQL 中页的结构, 页是真正存储记录的地方, 对应 B + 树中的一个节点, 也是 MySQL 中读写数据的最小单位, 页的结构设计也是相当有水平的, 能够加快数据的查询.
页结构
MySQL 中页是 innodb 中存储数据的基本单位, 也是 MySQL 中管理数据的最小单位, 和磁盘交互的时候都是以页来进行的, 默认是 16kb,MySQL 中采用 b + 树存储数据, 页相当于 b + 树中的一个节点.
页的结构如下图:
每个 Page 都有通用的头和尾, 但是中部的内容根据 Page 的类型不同而发生变化. Page 的头部里有我们关心的一些数据, 下图把 Page 的头部详细信息显示出来:
我们重点关注和数据组织结构相关的字段: Page 的头部保存了两个指针, 分别指向前一个 Page 和后一个 Page, 根据这两个指针我们很容易想象出 Page 链接起来就是一个双向链表的结构, 如下图:
再看看 Page 的主体内容, 我们主要关注行数据和索引的存储, 他们都位于 Page 的 User Records 部分, User Records 占据 Page 的大部分空间, User Records 由一条一条的 Record 组成. 在一个 Page 内部, 单链表的头尾由固定内容的两条记录来表示, 字符串形式的 "Infimum" 代表开头,"Supremum" 代表结尾, 这两个用来代表开头结尾的 Record 存储在 System Records 的, Infinum,Supremum 和 User Records 组成了一个单向链表结构. 最初数据是按照插入的先后顺序排列的, 但是随着新数据的插入和旧数据的删除, 数据物理顺序会变得混乱, 但他们依然通过链表的方式保持着逻辑上的先后顺序, 如下图:
把 User Record 的组织形式和若干 Page 组合起来, 就看到了稍微完整的形式.
innodb 为了快速查找记录, 在页中定义了一个称之为 page directory 的目录槽(slots), 每个槽位占用两个字节(用于保存指向记录的地址),page directory 中的多个 slot 组成了一个有序数组(可用于二分法快速定位记录, 向下看), 行记录被 Page Directory 逻辑的分成了多个块, 块与块之间是有序的, 能够加速记录的查找, 如下图:
看上图, 每个行记录的都有一个 n_owned 的区域(图中粉色区域),n_owned 标识所属的 slot 这个这个块有多少条数据, 伪记录 Infimum 的 n_owned 值总是 1, 记录 Supremum 的 n_owned 的取值范围为[1,8], 其他用户记录 n_owned 的取值范围[4,8], 并且只有每个块中最大的那条记录的 n_owned 才会有值, 其他的用户记录的 n_owned 为 0.
数据检索过程
在 page 中查询数据的时候, 先通过 b + 树中查询方法定位到数据所在的页, 然后将页内整体加载到内存中, 通过二分法在 page directory 中检索数据, 缩小范围, 比如需要检索 7, 通过二分法查找到 7 位于 slot2 和 slot3 所指向的记录中间, 然后从 slot3 指向的记录 5 开始向后向后一个个找, 可以找到记录 7, 如果里面没有 7, 走到 slot2 向的记录 8 结束.
n_owned 范围控制在 [4,8] 内, 能保证每个 slot 管辖的范围内数据量控制在 [4,8] 个, 能够加速目标数据的查找, 当有数据插入的时候, page directory 为了控制每个 slot 对应块中记录的个数([4,8]), 此时 page directory 中会对 slot 的数量进行调整.
对 page 的结构总结一下
b + 树中叶子页之间用双向链表连接的, 能够实现范围查找
页内部的记录之间是采用单向链表连接的, 方便访问下一条记录
为了加快页内部记录的查询, 对页内记录上加了个有序的稀疏索引, 叫页目录(page directory)
整体上来说 MySQL 中的索引用到了 b + 树, 链表, 二分法查找, 做到了快速定位目标数据, 快速范围查找.
本篇到此, 下一篇实战篇对 MySQL 索引使用上面做详细介绍, 喜欢的关注一下, 谢谢!
MySQL 系列目录
第 1 篇: MySQL 基础知识
第 2 篇: 详解 MySQL 数据类型(重点)
第 3 篇: 管理员必备技能(必须掌握)
第 4 篇: DDL 常见操作
第 5 篇: DML 操作汇总(insert,update,delete)
第 6 篇: select 查询基础篇
第 7 篇: 玩转 select 条件查询, 避免采坑
第 8 篇: 详解排序和分页(order by & limit)
第 9 篇: 分组查询详解(group by & having)
第 10 篇: 常用的几十个函数详解
第 11 篇: 深入了解连接查询及原理
第 12 篇: 子查询
第 13 篇: 细说 NULL 导致的神坑, 让人防不胜防
第 14 篇: 详解事务
第 15 篇: 详解视图
第 16 篇: 变量详解
第 17 篇: 存储过程 & 自定义函数详解
第 18 篇: 流程控制语句
第 19 篇: 游标详解
第 20 篇: 异常捕获及处理详解
第 21 篇: 什么是索引?
第 22 篇: MySQL 索引原理详解
MySQL 系列大概有 20 多篇, 喜欢的请关注一下, 欢迎大家加我微信 itsoku 或者留言交流 MySQL 相关技术!
来源: https://www.cnblogs.com/itsoku123/p/11660053.html