乐山市城乡规划建设局网站,微信小程序打不开怎解决,开发一个网站做爬虫,惠阳网站推广费用文章目录概述讨论范围查询数据结构查询数据结构种类及其高性能查询原理MySQL 索引的底层数据结构MySQL 索引的需求分析选择 MySQL 索引的底层数据结构B- 树和 B 树的对比MySQL 索引的底层数据结构揭秘概述
MySQL 的索引是存储引擎用于快速找到记录的一种数据结构#xff0c;是…
文章目录概述讨论范围查询数据结构查询数据结构种类及其高性能查询原理MySQL 索引的底层数据结构MySQL 索引的需求分析选择 MySQL 索引的底层数据结构B- 树和 B 树的对比MySQL 索引的底层数据结构揭秘概述
MySQL 的索引是存储引擎用于快速找到记录的一种数据结构是提升 SQL 执行效率的神器。 在正确建立及使用索引的情况下查询性能将会有非常大的提升从 ON 提升到 OlogN几乎接近于常数级别但在索引建立不正确或者使用不正确的情况下将会进行全表扫描ON查询性能就比较低下了。
讨论范围
为了不给读者带来可能的理解上的偏差以及困扰在这里首先说明本文中讨论的索引是 MySQL 中 InnoDB 存储引擎所使用的索引。
查询数据结构
为了方便大家理解 MySQL 索引的底层数据结构以及索引为什么能够提升查询性能首先从查询数据结构开始讲解。 查询数据结构光从字面上可能不太好理解。但是基于实际含义的角度上来看或许应该叫便于查询的数据结构又或者叫高性能的查询数据结构比较贴切。 即查询数据结构是一种能提升数据查询效率的数据结构。
查询数据结构种类及其高性能查询原理
常见的查询数据结构有以下几种
有序数组一个数组数组中的元素已经全部有序。利用其有序的性质使用二分查找可以获得 OlogN 时间复杂度的查询效率跳表一个链表单或双向都可以链表中的所有节点都有序且在原有链表的基础上增加了一级或多级索引。利用其有序索引性质使用二分查找可以获得 OlogN 时间复杂度的查询效率哈希表一种维护了键和值的唯一映射关系的数据结构其本质是将键通过哈希函数解决哈希冲突的某种手段散列到数组中的一种方法。利用数组的随机访问能力可以获得在最好情况下 O1 查询时间复杂度最坏情况的时间复杂度取决于哈希函数与解决哈希冲突的方法有关。二叉搜索树一种节点间有序的二叉树具体定义在这里就不展开讲了。利用其有序的性质使用二分查找在最好情况下可以获得 OlogN 时间复杂度的查询效率最坏情况下为 ON红黑树一种自平衡的二叉搜索树。利用其有序的性质使用二分查找可以获得 OlogN 时间复杂度的查询效率B- 树B- 树是一种自平衡的多叉搜索树。利用其有序的性质使用二分查找可以获得 OlogN 时间复杂度的查询效率B 树B 树也是一种自平衡的多叉搜索树。利用其有序的性质使用二分查找可以获得 OlogN 时间复杂度的查询效率
可以看出上面的数据结构除了哈希表外其余的数据结构都是利用了有序这个性质并结合二分查找方法即可获得较高的ON 时间复杂度查询效率。 唯一一个例外是二叉搜索树在最坏情况下在节点分布极其不均匀几乎退化成单向链表的情况下会退化成线性搜索其复杂度为 ON如下图所示
可以看到这个二叉搜索树几乎已经退化成了一条单向链表所以其查询时间复杂度将会是 ON。 所以我们得出一个结论想要提高查询效率最好利用一个数据有序且能自平衡或者不需要平衡操作的数据结构再结合二分查找方法即可达到目标。 在上面这个最重要的一点就是数据必须有序因为如果数据无序那么二分查找也无用武之地。
MySQL 索引的底层数据结构
假设你是 MySQL 的 InnoDB 存储引擎的开发人员你会选择哪种数据结构作为索引底层的数据结构呢
MySQL 索引的需求分析
想要实现一个功能首先得分析清楚这个功能的需求是什么。现在我们想要实现 MySQL 的索引那么索引的功能需求是什么呢 总的来说 MySQL 的索引有以下几个需求点
能够大幅度提升查询性能能支持范围查询易于维护维护的时间复杂度应该尽可能地低从磁盘读入内存的每个数据页应该包含尽可能多的信息能尽可能地减少磁盘 IO 次数
选择 MySQL 索引的底层数据结构
弄清楚需求后我们使用排除法来筛选所有可用的查询数据结构
有序数组不能满足 3、4、5排除。有序数组随机插入和删除元素的复杂度为 ON且有序数组在数据量较大时将数据从磁盘读入内存的 IO 次数将不可控跳表不能满足 4、5排除。跳表与有序数组相同从磁盘读入内存的每个数据页取决于数据本身的大小在数据量较大时将数据从磁盘读入内存的 IO 次数将不可控哈希表不能满足 2排除。哈希表不支持范围查询二叉搜索树不能自平衡排除红黑树不能满足 4、5排除。红黑树虽然能自平衡但是在数据量较大的情况下树的高度将会非常大将数据从磁盘读入内存的 IO 次数也会非常多B- 树基本可以满足所有条件B 树可以满足所有条件
经过上面的比对我们最终确定了 B- 树和 B 树两种数据结构可以满足我们的需求那么这两种数据结构哪种更适合用于实现 MySQL 的索引呢
B- 树和 B 树的对比
B- 树和 B 树两者都属于自平衡的多叉搜索树。但是从细节上来说两者之间有如下的区别
B 树只有在叶子节点上才会携带数据而 B- 树在每个节点上都会携带数据 这个特性决定了 B 树在非叶子节点上存储的关键字数量越多那么树的阶就会越大则树中的节点就会越少则树的高度就会越低树的高度越高则每次查询的时候需要进行的磁盘 IO 操作就会越多树的阶越大即非叶子节点上存储的关键字数量越多则从磁盘读入内存的每个数据页所包含的信息数量就越多 B 树对于范围查询的性能更高 B 树的所有叶子节点组成了一个有序的链表在进行范围查询时只需要遍历叶子节点组成的链表就行B- 树在进行范围查找时需要反复地中序遍历才能获得范围内的所有数据
下面的图说明了在存储同一组数据时B- 树和 B 树的区别 在这里我们模拟 B- 树因为所有节点都要存储数据所以阶为 3 的情况而 B 树只有在叶子节点上才会存储数据所以阶会比 B- 树要大这里设定为 4。 可以看到在存储同一组数据时B- 树的高度比 B 树要高且 B 树的所有叶子节点组成了一个有序链表范围查询时更方便也更高效。
MySQL 索引的底层数据结构揭秘
根据上面的分析我们可以得出要实现 MySQL 索引底层数据结构选择 B 树最为合适。而实际上MySQL 的 InnoDB 存储引擎也确实是使用 B 树作为底层的数据结构的。 而 InnoDB 除了实现标准的 B 树功能外还有以下的实现细节值得关注
InnoDB 数据页的大小由参数 innodb_page_size 决定决定了 B 树的节点的大小也决定了这个节点上存储的关键字数量 默认的一个页的大小为 16KB高度为 3 的 B 树即可存储千万级别的数据量 叶子节点组成的链表为双向链表可以更方便也是更高效地处理范围查询
