B树

B树的定义

• 所谓m阶B树是所有结点的平衡因子均等于。的m路平衡查找树。
• 一棵成阶B树或为空树，或为满足如下特性的m叉树:
  • 树中每个结点至多有％棵子树，即至多含有彻-1个关键字。
  • 若根结点不是叶结点，则至少有两棵子树。
  • 除根结点外的所有非叶结点至少有「m/2⌉棵子树，即至少含有⌈m/2⌉-1个关键字。
  • 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。
    
    
    

B树的查找

• 在B树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。
• B树的查找包含两个基本操作:①在B树中找结点；②在结点内找关键字。由于B树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。

B树的高度

总结