深入解析B树算法及其Python实现

B树算法详解 Python实现B树

B树,和二叉搜索树很像,每个节点可以包含多个节点,但B树的子节点可以超过两个。

B树数据结构

B树可以在单个节点中存储许多键,并且可以有多个子节点。

B树搜索算法

BtreeSearch(x,k)
i=1
while i≤n[x]and k≥keyi[x]
do i=i+1
if i n[x]and k=keyi[x]
then return(x,i)
if leaf[x]
then return NIL
else
return BtreeSearch(ci[x],k)

登录后复制

B树搜索示例

指定K=17,从根节点开始,将k与根进行比较。

ķ>11,转到根的右子节点;比较k和16,因为>16,比较k和下一个键18。

由于k