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
