B树与B+树

B树与B+树

• B树的叶结点对应查找失败的情况，对有n个关键字的查找集合进行查找，失败的可能性有n+1种

• 结点最少时，三阶B树形状至少类似于一棵满二叉树

  • 结点最多时，三阶B树形状类似于满三叉树

• B树和B+树的差异主要体现在

  • 结点关键字和子树的个数
  • B+树非叶结点仅起索引作用
  • B树叶结点关键字和其他结点包含的关键字是不重复的
  • B+树支持顺序查找和随机查找；而B树仅支持随机查找

• B树的叶结点不要求用指针链接，B+树的叶结点使用指针链接起来

• B+树是应文件系统所需而产生的 B 树的变形。前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，

  • 因为前者的磁盘读写代价更低，查询效率更加稳定。
    • 编译器中的词法分析使用有穷自动机和语法树。
    • 网络中的路由表缺速查找主要靠高速缓存、路由表压缩技术和快速查找算法。
    • 系统一般使用空闲空间链表管理磁盘空闲块。