目录一、产生的背景1.1 进化要求二、B-tree2.1 B-tree特性三、B+tree3.1 B+tree特性四、结论一、产生的背景 二叉查找树的查找时间复杂度是O(logN),整体的查询效率已经足够高了,那么为什么
二叉查找树的查找时间复杂度是
O(logN)
,整体的查询效率已经足够高了,那么为什么还会有B树和B+树的进化演进呢? 主要的原因是:二叉树可能会退化成一个线性树,造成磁盘io次数增高的问题,当有大量的数据存储的时候,二叉查找树查询不能将所有的数据加载到内存中,只能逐一加载磁盘页,每个磁盘对应树的节点,造成大量的磁盘IO操作(最坏的情况IO次数为树的高度),平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁,进而导致效率低下。所以,为了减少磁的IO的次数,必须降低树的深度,将瘦高
的树变得矮胖
。
B-Tree是一种多叉的平衡搜索树(并不一定是二叉的),以一个三阶B-tree为例子来分析,每个储存块都包含:关键字和指向孩子结点的指针,最多有M个孩子,M的大小主要取决于每个存储块的容量和数据库的配置
,M表示M阶数的意思。
ceil(M/2)
个孩子节点,ceil是取上限函数(M是阶数,3阶,即:每个节点至少有2个孩子);假设每个非叶子节点包含n个关键字信息,其中:
K(i-1)< Ki
;[ceil(m/2)-1]<=n<=m-1
(非叶子结点的关键字 = 指向孩子的指针个数-1);(K[i-1],K[i])
的子树,是开区间(即:9和10都处于8-12区间);假设需要查询数据15,查询步骤:
B+树是B树的变体,其定义基本上与B树相同,除了:
[K[i],K[i+1])
的子树,左闭右开区间;矮壮
,能存储更多数据。B+tree相比B-tree更适合用来存储索引,原因如下:
任何关键字查询都是从根节点到叶子节点的查询路线,因此每个数据的查询效率都是稳定一致的
。到此这篇关于Mysql B-tree与B+tree索引数据结构剖析的文章就介绍到这了,更多相关mysql B-tree与B+tree内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!
--结束END--
本文标题: MySQL B-tree与B+tree索引数据结构剖析
本文链接: https://www.lsjlt.com/news/33790.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-05-09
2024-05-09
2024-05-09
2024-05-09
2024-05-08
2024-05-08
2024-05-08
2024-05-08
2024-05-08
2024-05-08
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0