企业站群cms官网免费,wordpress集成后台无法登录,深圳排名seo,个体营业执照网上年报MySQL 索引底层探索#xff1a;为什么是B树#xff1f; 1. 由一个例子总结索引的特点2. 基于哈希表实现的哈希索引3. 高效的查找方式#xff1a;二分查找4. 基于二分查找思想的二叉查找树5. 升级版的BST树#xff1a;AVL 树6. 更加符合磁盘特征的B树7. 不断优化的B树#… MySQL 索引底层探索为什么是B树 1. 由一个例子总结索引的特点2. 基于哈希表实现的哈希索引3. 高效的查找方式二分查找4. 基于二分查找思想的二叉查找树5. 升级版的BST树AVL 树6. 更加符合磁盘特征的B树7. 不断优化的B树B 树8. 疑问和思考8.1 B 树和 B 树的区别 9. 参考文档 你可能已经知道 B 树被用于 MySQL 的Innodb引擎的索引底层实现那么为什么是 B 树呢本文由浅及深探索数据库索引底层实现。
关于常见分布式组件高可用设计原理的理解和思考 1. 由一个例子总结索引的特点
加索引是数据库加速查询的一种方式那么为什么用索引可以加快查询呢讲到索引其实我们经常会听到一个图书馆的例子图书馆里的书目繁杂我们如何从若干本书里面找到一本我们想要的书呢我们根据图书馆系统检索可以找到某本书对应的图书编号。在基于书籍按照一定规则排列的前提下我们可以根据图书编号找到这本书。
例如假设图书编号根据
第几个书架 - 书架上第几个格子第几层 - 从左到右数第几个位置这样的规则编排我们就可以轻松的获取到我们想要的书籍。
你也许发现了这个例子中藏着两个信息
按照一定的规则排列有序
按照一定的规则建立一定的映射关系这让你联想到了什么没错就是哈希表。
2. 基于哈希表实现的哈希索引
探讨哈希索引相关特性。
在 MySQL 的 InnoDB 引擎中自适应哈希索引就是用哈希表实现的。哈希索引是数据库自身创建并使用的DBA 本身不能对其进行干预但是可以通过参数来禁止或者启用此特性。
显然用哈希表实现索引的好处是非常明显的查找单个指定数据只需要O(1)的时间复杂度。列入如下sql语句
select id from tablename where id 1;但是对于这种查找指定范围的 sql 语句哈希索引就无能为力了。
select id from tablename where id BETWEEN 20 AND 23;原因是哈希这种数据结构本身是无序的因此针对数据排序难以获取好的效果 到这里我们遇到了一个问题就是哈希表虽然从查找效率上满足了我们查找单个数据的要求但是显然当遇到范围查询时由于哈希表本身的无序性不利于指定范围查找。因此我们需要针对这种类型的查询获取更加友好的数据结构方式以获取更好的查询性能。
也就是说我们的需求增加了我们希望数据的组织方式既要有一定规则又要有序。在引出这种数据结构之前我们首先来看一种查找方式二分查找。
3. 高效的查找方式二分查找
二分查找的核心思想是给定一个 有序 的数组在查找过程中采用跳跃式的方式查找即先以有序数列的中点位置为比较对象如果要查找的元素小于中点元素则将待查序列缩小为左半部分否则为右半部分。通过每次比较将查找区间减少一半直到找到所需元素。
比如要从以下序列中查找到数字 4
[1,3,4,5,6,7,8]需要经过下面的查找步骤
取中心位置对应元素显然 5 大于 4在左边区间 [1,3,4] 进行查找继续取中心位置对应元素 3显然 3 大于 4,在右边区间 [4] 进行查找4 等于 4所以我们查找成功。
可以看到二分查找的效率是 O(log n)。
由于有序数组自身的有序性所以范围查询依然可以通过二分查找的方式查找区间的边界来实现。 这样看来如果单从查询效率上来说有序的数组是一种很好的选择。但是显然有序数组对于插入和删除并不友好假设我们要插入元素或者删除元素都需要把部分元素全部向后或者向前移动最糟糕的时间复杂度是 。
有没有这样一种数据结构既有一定顺序又方便插入和删除呢事实上基于二分查找的思想诞生了这样一种数据结构二分查找树。
4. 基于二分查找思想的二叉查找树
二叉查找树Binary Search Tree即BST树是这样的一种数据结构,如下图 在二叉搜索树中
若任意结点的左子树不空则左子树上所有结点的值均不大于它的根结点的值。若任意结点的右子树不空则右子树上所有结点的值均不小于它的根结点的值。任意结点的左、右子树也分别为二叉搜索树。
这样的结构非常适合用二分查找的思维查找元素。
比如我们需要查找键值为8的记录
先从根找起找到 6显然 86所以接着找到 6 的右子树找到 7显然 87, 所以找 7 的右子树找到了 8查找结束。
这样一棵子树高度差不大于 1 的二叉查找树的查找效率接近与O(logn);
但是当二叉树的构造变成这样时, 此时我们再查找 8 时,查找效率就沦为接近顺序遍历查找的效率。 显然这不是我们想要的二叉查找树也需要 balance以控制二叉树的层高和规格配置
5. 升级版的BST树AVL 树
我们对二叉查找树做个限制限制必须满足任何节点的两个子树的最大差为 1也是AVL 树的定义这样我们的查找效率就有了一定的保障。AVL 树 是一种自平衡二叉查找树(self-balancing binary search tree)。
当然维护AVL 树也是需要一定开销的即当树插入/更新/删除新的数据时假设破坏了树的平衡性那么需要通过左旋和右旋来维护树的平衡。当数据量很多时同样也会出现二叉树过高的情况。
我们知道AVL 树的查找效率为 O(log n)也就是说当树过高时查找效率会下降。
另外由于我们的索引文件并不小所以是存储在磁盘上的。文件系统需要从磁盘读取数据时一般以页为单位进行读取假设一个页内的数据过少那么操作系统就需要读取更多的页涉及磁盘随机 I/O 访问的次数就更多。
将数据从磁盘读入内存涉及随机 I/O 的访问是数据库里面成本最高的操作之一。因而这种树高会随数据量增多急剧增加每次更新数据又需要通过左旋和右旋维护平衡的二叉树不太适合用于存储在磁盘上的索引文件。
因此我们应该尽可能的减少文件系统的随机访问解决的思路应该是
一个文件系统页应该尽可能的保存多的数据以减少页的数量访问提升效率减少树的层高
6. 更加符合磁盘特征的B树
前面我们看到虽然AVL树既有链表的快速插入与删除操作的特点又有数组快速查找的优势但是这并不是最符合磁盘读写特征的数据结构。
也就是说我们要找到这样一种数据结构能够有效的控制树高那么我们把二叉树变成m叉树也就是下图的这种数据结构:B 树。
B树是一种这样的数据结构 根结点至少有两个子结点;
每个中间节点都包含 k-1 个元素和k个子结点其中 m/2 k m;每一个叶子结点都包含 k-1 个元素其中 m/2 k m;所有的叶子结点都位于同一层;每个结点中关键字从小到大排列并且当该结点的孩子是非叶子结点时该 k-1 个元素正好是 k 个子结点包含的元素的值域的分划。
可以看到B树在保留二叉树预划分范围从而提升查询效率的思想的前提下做了以下优化
二叉树变成 m 叉树这个 m 的大小可以根据单个页的大小做对应调整从而使得一个页可以存储更多的数据从磁盘中读取一个页可以读到的数据就更多随机 IO 次数变少大大提升效率。但是我们看到我们只能通过中序遍历查询全表当进行范围查询时可能会需要中序回溯。如果出现查询回溯就会导致查询的路径层高变高随机IO次数进一步提升。
因此需要针对B树进一步调整
7. 不断优化的B树B 树
基于以上的缺陷又诞生了一种新的优化B树的树: B 树 B树在B树的基础上加了以下优化
叶子结点增加了指针进行连接即叶子结点间形成了链表非叶子结点只存关键字 key不再存储数据只在叶子结点存储数据
说明叶子之间用双向链表连接比单向链表连接多出的好处是通过链表中任一结点都可以通过往前或者往后遍历找到链表中指定的其他结点。
这样做的好处是
范围查询时可以通过访问叶子节点的链表进行有序遍历而不再需要中序回溯访问结点。非叶子结点只存储关键字key一方面这种结构相当于划分出了更多的范围加快了查询速度另一方面相当于单个索引值大小变小同一个页可以存储更多的关键字读取单个页就可以得到更多的关键字可检索的范围变大了相对 IO 读写次数就降低了。
8. 疑问和思考
一些总结
8.1 B 树和 B 树的区别
B 树非叶子结点和叶子结点都存储数据,因此查询数据时时间复杂度最好为 O(1),最坏为 O(log n)。 B 树只在叶子结点存储数据非叶子结点存储关键字且不同非叶子结点的关键字可能重复因此查询数据时时间复杂度固定为 O(log n)。
B 树叶子结点之间用链表相互连接因而只需扫描叶子结点的链表就可以完成一次遍历操作B树只能通过中序遍历。
为什么 B 树比 B 树更适合应用于数据库索引 B 树更加适应磁盘的特性相比 B 树减少了 I/O 读写的次数。由于索引文件很大因此索引文件存储在磁盘上B 树的非叶子结点只存关键字不存数据因而单个页可以存储更多的关键字即一次性读入内存的需要查找的关键字也就越多磁盘的随机 I/O 读取次数相对就减少了。
B 树的查询效率相比B树更加稳定由于数据只存在在叶子结点上所以查找效率固定为 O(log n)。 B 树叶子结点之间用链表有序连接所以扫描全部数据只需扫描一遍叶子结点利于扫库和范围查询B 树由于非叶子结点也存数据所以只能通过中序遍历按序来扫。
也就是说对于范围查询和有序遍历而言B 树的效率更高。
9. 参考文档
暂无
