数据结构:2-3树、B树、B+树、B*树

数据结构 大约 678 字

多路查找树

muitl-way search tree

在二叉树中,每个节点最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多路查找树,也叫多叉树。

节点的度

节点的子节点有几个。

树的度M

节点的度的最大值。

2-3树(二三树)

23 tree.png

满足排序树的特点。

2-3树是最简单的B树。

2-3树所有叶子节点都在同一层(只要是B树都要满足所有节点在同一层这个条件)。

有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点。

有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点。

2-3树由二节点和三节点组成。

2-3-4树和2-3树类似,也是一种B树。

B树

B Tree.png

注意:B-树,不是B减树,就是B树!

B:是Balance平衡的意思,不是Binary

可以在非叶子节点命中数据。

B树的阶

节点的最多子节点的个数,比如2-3树的阶就是32-3-4树的阶就是4

B+树

BTree.png

所有数据都在叶子节点的链表中,不可能在非叶子节点命中。

叶子节点有一个指针指向下一个叶子节点,所有适合范围查询(MySQL范围查询时适合建立B+Tree索引,等值查询时适合Hash索引)。

数据只能在叶子节点,也叫稠密索引。

非叶子节点相当于叶子节点的索引,稀疏索引。

更适合文件系统。

B*树

B星树.png

B*树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针。

非叶子节点关键字个数至少为(2/3)*M,即块的最低使用率为2/3,而B+树的块的最低使用率为B+树的1/2

B*树分配新节点的概率比B+树要低,空间使用率更高。

阅读 24 · 发布于 2021-02-22

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批