数据结构 - 多路搜索树(2-3树、b树、b+树、b*树)

野性酷女 2023-07-03 08:10 27阅读 0赞

如果二叉树的高度太高，速度还是比较慢

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2-3树 实现步骤

数列：[16,24,12,32,26,34,10,8,28,38,20]

第一步：16直接放到一个2节点

第二步：24放到16后面

第三步：12不能放到16前面，要不然不满足2-3树变成4叉了，所以要拆

第四步：32放到16后面，然后放到24后面

在这里插入图片描述

第五步：26放到24和32中间变成四叉不满足，如果放到24-32下面当成中间节点，只有一个子节点不满足，所以放到上面去

在这里插入图片描述
在这里插入图片描述

第六步：34直接放到32后面

在这里插入图片描述

第七步：10放到12前面不行会变成四叉，放到12下面只有一个节点，所以要拆分，

但是拆分完后不满足b树的所有叶子节点在同一层，不满足，所以要进行调整

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

B+树：数据只在叶子节点的链表中存储，数据只能在叶子节点（稠密索引）且叶子节点链表中的数据是有序的，非叶子节点相当于叶子节点的索引（稀疏索引）；

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读