请你讲讲 B 树和 B+ 树

[问答题]

请你讲讲 B 树和 B+ 树

卧槽型选手

B树是一颗平衡多路查找树，我们一般使用阶数表示一个B树的最大分叉数目。和一般的查找树不同的是，它一个节点可以有可以有多个键值，可以有多个子树。因此在节点数量相同，B树的高度要比二叉查找树矮。因为磁盘IO最大次数由树的高度决定，B树的效率要比普通的二叉树高。 B+树是B树的变种，主要区别是B+树的非叶子节点只存放指针，实际的值存放在叶子节点上，好处在一个节点大小不变的情况下，可以存放更多的键值，提高树的阶数。我们知道阶数越高，树越矮，访问磁盘的次数越少，性能越好。而且叶子节点之间使用链表相连，便于区间查找和遍历，B树则需要进行递归遍历，效率更低。

发表于 2022-10-29 21:34:58 回复(0)

牛客116077496号

(ᇂ_ᇂ|||)

发表于 2022-07-20 20:23:51 回复(0)

大角牛fafasf

歪日，第一次听说

编辑于 2024-03-08 10:49:03 回复(2)

时七❀

B树，又称多路平衡查找树，每个节点可能有多个分叉，是一种绝对平衡，任何节点的所有子树高度相同。m阶B树可以是空树，也可以是满足以下条件的m叉树：1.每个节点至多有m棵子树，即至多含有m-1个关键字 2.若根节点不是终端节点，则至少有两棵子树 3.除根节点外的所有非叶节点至少有[m/2]向上取整棵子树，即至少含有[m/2]-1个关键字

发表于 2023-03-27 11:34:05 回复(0)

moon009

B+树存的也是k-1个值 k个指针吧

发表于 2023-02-24 10:15:44 回复(0)