数据结构 - 多路搜索树(2-3树、b树、b+树、b*树)
分类:
文章
•
2025-04-06 20:41:22
如果二叉树的高度太高，速度还是比较慢
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+树：数据只在叶子节点的链表中存储，数据只能在叶子节点（稠密索引）且叶子节点链表中的数据是有序的，非叶子节点相当于叶子节点的索引（稀疏索引）；
