智林东莞网站建设公司,免费软件大全下载安装,项目建设全过程,网站规划与开发技术专业GOOD NIGHT前言上一篇中#xff0c;我们已经了解到了索引的基本概念和一些用法。那索引为什么会提升查询的速度#xff0c;以及索引究竟是怎么工作的呢#xff1f;也许大家心里还是有一些迷茫#xff0c;这一切#xff0c;还要从索引背后的算法说起。GOOD NIGHT概述大家知… GOOD NIGHT前言上一篇中我们已经了解到了索引的基本概念和一些用法。那索引为什么会提升查询的速度以及索引究竟是怎么工作的呢也许大家心里还是有一些迷茫这一切还要从索引背后的算法说起。GOOD NIGHT概述大家知道数据库的索引和数据一般都是存储在硬盘中的这样利于数据的持久化和永久保存。因此在我们查找数据的时候就会产生硬盘的I/O操作。而硬盘相较于内存而言速度是比较慢的所以如何减少硬盘的I/O操作就是索引背后的算法存在的意义。GOOD NIGHT二分法二分法是一种常用的查找算法相较于逐个遍历查找而言二分法的时间复杂度为O(log2n)。为了帮助大家理解和回忆二分查找我画了一张二分查找的流程图从上述流程来看我们要事先对要查找的数组或集合进行排序而且每次会寻找中间节点进行范围的划分和对数字的比较。那么我们能不能把这个过程进行简化呢二叉搜索树(Binary Search Tree)会给你答案。GOOD NIGHT二叉搜索树如上文所述二叉搜索树的特征是有序且预先把数据进行分段存储并且将中间节点作为树的根节点那么我们会得到如下的二叉树结构这里以数组[7,25,36,50,64,78,87]为例创建出来的二叉树如下所示我们可以看出一些特征对于每个节点而言它的左孩子都小于它的父节点而右孩子都大于它的父节点。所以我们把这样的二叉树叫做二叉搜索树(Binary Search Tree)。二叉搜索树重复利用了二分法的思想来查找数据但有时由于构造树时产生问题导致同样的数据插入顺序不一样二叉搜索树就会变成如下结构从两张图的比较中我们不难看出图一的树高度为3也就是最多只需要3次比较就能找出节点而图二的树的结构会变成线性需要7次比较查找时的复杂度也会瞬间提升为O(n)。所以为了解决二叉树不平衡的问题人们又提出了新的数据结构叫做平衡二叉搜索树(AVL树)。GOOD NIGHT平衡二叉搜索树刚才我们提出了要解决二叉树的不平衡问题就需要一个可以在每次插入或者删除节点时都可以做到自动平衡的二叉树结构也叫平衡二叉搜索树。平衡二叉搜索树的核心思想就是计算每个节点的平衡因子balance factor平衡因子的定义是一个节点的左孩子的高度减去其右孩子的高度这里的高度height就是指从一个节点出发到达最远叶子节点所经过的最长路径。如我们上述的图一中从根节点50到达子节点36的高度即为2。通过上面的概念我们可以发现当一个节点的平衡因子绝对值大于等于1时树就不再平衡所以这里平衡二叉树还包含了一个旋转的机制在此不表感兴趣的同学可以自行查找进行理解。那么我们在讲了这么多之后平衡二叉搜索树是不是就可以作为索引背后的数据结构来进行存储了呢这里再使用一张图来直观说明一下我们前文提到了查找数据是走了硬盘的I/O操作那么对于这棵二叉树来说树的高度为5最坏的情况下需要查找5次。这就意味着如果树的高度越高那么硬盘的I/O次数也会越多。所以我们有没有办法去降低树的高度呢可以遵循这样的思路去思考如果一个节点下不止2个子节点而是多个那么整体的高度就可以降低。比如我们将二叉树改为三叉树这个时候同样的节点数量我们的树高度则降为了4也就是说最多需要4次I/O即可找到需要查找的内容。所以我们可以将二叉树改为M叉树(M2)即一个节点下有M个子节点这样当数据量大小为N时M叉树的高度将会远远小于二叉树的高度这样就引申出了B树的概念。GOOD NIGHT什么是B树B树的英文全名为Banlance Tree翻译过来为平衡多路搜索树我们从上文中已知当一个节点有多个子节点时高度会下降因此B树很适合用于查询在文件系统和数据库系统中的索引常常会使用B树来实现。在这里有一个概念纠正下有些书中或博客会提到B-树而实际上B-树和B树是同一种结构只是翻译名称上存在一些误解。B树的结构如图所示B 树作为平衡的多路搜索树它的每一个节点最多可以包括 M 个子节点M 称为 B 树的阶。每个节点中都存储了关键字和子节点的指针。对于一个 100 阶的 B 树来说如果有 3 层的话最多可以存储约 100*100* 100100 万的索引数据。B树的特性有以下几点1、所有节点关键字是按递增次序排列并遵循左小右大原则。2、树中的每个节点至多有M个子节点即至多有M-1个关键字(二叉树有2个子节点和1个关键字)。3、除根节点外其他节点至少有M/2个子节点。4、若根节点不是叶子节点则根节点至少有2个子节点。5、所有叶子节点均在同一层所以B树是一个所有平衡因子均为0的多路查找树。以上图为例根节点中有2个关键字17和35以及3个子节点指针P1、P2和P3。而且在第二层最左侧的子节点中有2个关键字8和12包含了3个子节点。子节点1中的关键字为3和5都小于8而子节点2中的关键字为9和10大于8小于12子节点3中的关键字为13和15均大于12都符合我们上述提到的特性。如果我们使用B树进行查找关键字9那么可以分为以下几步1、先与根节点进行比较9小于17那么我们可以得到指针P1继续从子节点中进行查找2、在子节点中9大于8而小于12此时可以得到指针P2继续往下查找3、在最后一层的子节点中找出关键字9结束查找。可以看出相较于平衡二叉树而言B树查找时的磁盘I/O要少整体查询效率也要高出很多。看到这里相信大家已经大致明白了索引背后的工作原理B树已经很适合作为索引的算法。但实际上在MySQL中还会使用B树索引这又是为什么呢GOOD NIGHTB树的改进相较于B树而言B树在两个方面又做出了改进和提升一方面是查询的稳定性另一方面是查询的效率更高。B树的结构如下图所示与B树相比B树的非叶子节点不保存具体的数据而只保存关键字的索引所有的数据都会保存至叶子节点。因为所有数据必须要到叶子节点才能获取到所以每次数据查询的次数都一样这样一来B树的查询速度也就会比较稳定。在B树中非叶子节点的子节点数关键字数如上图所示根节点有2个关键字对于的也有2个子节点。这样的好处是一个节点可以存储更多的关键字阶数会更大高度会更低查询效率也就更高。B树查找关键字的方式与B树类似先从关键字中找出范围和指针然后找到对应的子节点一级一级往下查询直到最终的叶子节点查出所需要的数据。由于B树的数据都存储在叶子节点所以更有利于数据库做全表扫描不需要像B树一样逐层扫描而是直接遍历所有的叶子节点即可。GOOD NIGHT总结今天我们从最基本的二分查找开始逐步分析了各种查找树的工作原理和优缺点不断改进从而挖掘出最终的B树和B树算法深刻理解了索引背后的工作原理。虽然传统的二叉树查询的效率也很高但是很容易增加磁盘I/O的次数影响索引使用的效率所以我们最终会采用降低树高度的方式来构造索引。在实际工作中我们使用索引也许不会直接去编写B树和B树的算法。但是学习这些算法会有助于我们增强逻辑思考的能力还可以提升一些设计方面的能力对于“修炼内功”会很有帮助希望大家可以在这条路上持之以恒。下一期将是索引系列的最终篇章我们会结合实际工作中的复杂SQL场景合理使用索引和改写原有语句以避免全表扫描来对数据库进行优化敬请期待您的点赞和在看是我创作的最大动力感谢支持公众号wacky的碎碎念知乎wacky
