网站定制设计师,服装企业北京网站建设,公司展示网站制作,网站建设后端前端文章目录 简介如何评价索引的数据结构设计好坏二叉树的局限性什么是B树什么是B树总结参考文献 简介
我们在上一节中说过#xff0c;索引其实是一种数据结构#xff0c;那它到底是一种什么样的数据结构呢#xff1f;本节将简单介绍一下几个问题#xff1a;
什么样的数据结… 文章目录 简介如何评价索引的数据结构设计好坏二叉树的局限性什么是B树什么是B树总结参考文献 简介
我们在上一节中说过索引其实是一种数据结构那它到底是一种什么样的数据结构呢本节将简单介绍一下几个问题
什么样的数据结构更适合作为索引平衡二叉树是否合适什么是B树和B树为什么我们常用B树作为索引的数据结构
如何评价索引的数据结构设计好坏
由于索引是存放在磁盘上的所以我们在通过索引来查找某行数据的时候大量的时间其实是花在了磁盘的IO上。
因此如果我们能让索引的数据结构尽量减少与磁盘的IO次数那么就能减少查询所消耗的时间这样的数据结构就是更好的。
二叉树的局限性
二叉树是一种高效且常见的数据检索方式。其时间复杂度为O(log2N)那么采用二叉树作为索引的数据结构合适么
让我们看一下最基础的二叉搜索树假设需要搜索的数值是key
如果key大于根节点则在右子树中进行查找如果key小于根节点则在左子树中进行查找如果key等于根节点那么就是找到了这个节点。
举个例子3422895237791创造出来的二叉搜索树为 最多只需要经过3次搜索就能找到指定值。
但是存在特殊的情况比如说以(5, 22, 23, 34, 77, 89, 91)的顺序创造出来的二分查找树为 在这个树里最多需要经过7次比较之后才能找到指定的节点。
因为第二棵树实际上已经退化成了一张链表查找数据的时间复杂度变成了O(n)。
当然如果使用平衡二叉搜索树的话就可以解决这个问题因为平衡二叉数在二分搜索树的基础上添加了约束其约定每个节点的左子树和右子树的高度差不能超过1即左右子树依然是平衡二叉树。
常见的平衡二叉树有很多种比如说平衡二叉搜索树、红黑树、数堆、伸展树。平衡二叉搜索树是最早提出的一种平衡二叉树。因此我们一般说的平衡二叉树其实就是平衡二叉搜索树搜索时间复杂度就是 O ( l o g 2 n ) O(log_2n) O(log2n)。
由于每访问一次节点就要进行一次磁盘IO操作所以对平衡二叉搜索树来讲一般会进行 O ( l o g 2 n 1 ) O(log_2n1) O(log2n1)次IO操作。比如说一个5层的平衡二叉树共31个节点正常会进行5次IO操作。树的深度越大意味着IO操作的次数就越多就越影响整体数据查询的效率。
所以我们可以考虑下如果将二叉树换成M叉树M2是不是就可以降低树的高度了呢比如说同样的31个节点使用三叉树来存储的话树深就变成了 l o g 3 ( 31 1 ) log_3(311) log3(311)就是4层。
可以看到此时树的高度降低了当数据量足够大的时候确实比二叉树要好一些。
什么是B树
上一小节中我们讲到了M叉树M2的表现要优于二叉树。因此一个节点应该允许有M个子节点。
B树就是这么被提出来的。B树即Balance Tree就是平衡的多路搜索树它的高度远小于平衡二叉搜索树的高度。在文件系统和数据库系统中的索引结构经常使用B树来实现。
B树的结构如下图 可以看到B树中每个节点最多可以包含M个子节点而M则称为是B树的阶。
同时每个磁盘块中包括了关键字如17/35和子节点的指针如P1、P2和P3。指针数是关键字数量 1。
对一个100阶的B树来讲如果有3层的话最多可以存储 99 ∗ 1 99 ∗ 10 0 1 99 ∗ 10 0 2 999999 99*1 99*100^1 99*100^2999999 99∗199∗100199∗1002999999约100w的索引数据。
在存储数据相同的情况下其高度远远低于二叉树的高度。
简单总结下一个M阶B树M2的特性
根节点的孩子节点数为[2, M]每个中间节点包含n-1个关键字和n个孩子其中n的取值范围是[ceil(M/2)M]假设中间节点的关键字为 k 1 , k 2 , . . . . , k n − 1 k_1, k_2,....,k_{n-1} k1,k2,....,kn−1且关键字按照升序排序即 k i k i 1 k_i k_{i1} kiki1。此时n-1个关键字相当于是划分出了n个数值范围因此对应着n个指针即 P 1 , P 2 , . . . . , P n P_1, P_2,....,P_n P1,P2,....,Pn其中 P 1 P_1 P1指向关键字小于 K 1 K_1 K1的子节点 P 2 P_2 P2指向关键字属于 ( k 1 , k 2 ) (k_1, k_2) (k1,k2)的节点以此类推。所有叶子节点位于同一层。
可以结合上面图来查看刚刚总结的这些特性。
相比平衡二叉树B树的深度要更低从而要进行的磁盘IO操作也更少在数据查询中的效率就显得更高。
虽然M越大一次读进内存的用来比较的数据就越多但这个比较的过程是在内存里进行的时间消耗可以忽略不计。
什么是B树
B树是对B树的改进主流的DBMS都支持B树的索引方式比如说MySQL。
B树和B树的差异在哪儿呢
每个节点内的关键字数量和孩子数量一样。而B树中孩子数量 关键字数量 1非叶子节点的关键字也会同时出现在子节点里并且是子节点关键字里的最大或者最小。而B树中则不会同时出现在子节点中非叶子节点仅用于索引不保存数据记录所有的数据记录都是放在叶子节点里。而B树中所有的节点都是可以既保存索引也保存数据记录。所有关键字都在叶子节点里出现每个节点内部所有关键字按照大小从小到大顺序排列所有叶子节点构成一个有序链表。
比如说下面这张图就是一棵B树 比如说想查找关键字16就会自顶向下逐层进行查找先后访问磁盘块1、磁盘块2、磁盘块7。三次IO操作即可。
在IO的次数上B 树看起来似乎跟B树差不多那么B树到底好在哪儿呢
这个要看B树和B树的根本差异B树的中间节点并不直接存储数据。
这样有什么好处呢
首先B树查询效率更加稳定。B树每次只有访问到叶子节点后才能取出数据而B树中由于非叶子节点也可以存储数据这就造成了查询效率不稳定的情况有时候需要访问到叶子节点才能找到数据有时候走一半到非叶子节点就可以找到数据。时间不好量化。
其次B树查询效率更高。通常B树比B树更矮胖非叶子节点只存放索引因此一个节点可以放更多关键字从而减少深度所需的磁盘IO就更少。同样的磁盘页大小B树可以存储更多的节点关键字。
在做区间查询的时候B树的效率同样比B树高。因为B树里所有的关键字都出现在叶子节点上并通过有序链表进行了链接非常适合寻找范围数据。而B树则需要通过中序遍历扫一遍才能完成范围数据的查找效率要低很多。
总结
索引在使用时时间的消耗主要是两部分带来的一是读取磁盘块来取出里面保存的索引值数据二是比较索引值数据。不过比较的工作是在内存中进行的速度很快所以这部分时间其实可以忽略不计。
因此制约索引使用速度的唯一因素就是与磁盘块的IO。只要能减少这块的IO就能减少索引在使用时的时间消耗从而提升整个查询的效率。
构造索引的时候我们更倾向于采用矮胖的数据结构因此平衡二叉树的结构被果断舍弃了。
B树和B树都可以作为索引的数据结构在MySQL中采用的是B树其查询性能更加稳定在磁盘页大小相同的情况下树的构造更加矮胖所需要的IO次数更少也更适合进行关键字的范围查找。
参考文献
24丨索引的原理我们为什么用B树来做索引
