数据结构 - 多路搜索树(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人围观)

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

相关阅读