B树是为磁盘或其他辅助存储设计的一种平衡搜索树。
我理解B树与红黑树等的主要区别是，红黑树假定对树的操作都在内存中，定义两种操作：
1.关键字与结点的比较
2.在树中沿树的结构爬升或下降
红黑树在内存进行这两种操作的时间在同一个数量级内
而在磁盘等辅助存储设备的状况下，这两种操作的时间相差多个数量级，爬升和下降操作耗时巨大，所以设计了B树来增加操作1，减少操作2
B树的主要特性就是分支因子很大，树的高度很小，极大的减少了操作2
B树的定义
B树的严格定义有很多项，简单的说，B树是一颗分支因子很大的搜索树，可以想象为 n 叉搜索树（相对于二叉搜索树）
可以证明，严格定义的B树高度会很小，比二叉搜索树小的多
B树上的基本操作
基本操作包括搜索、创建、插入
搜索的过程较简单，是一个从跟结点向下查找的过程，与二叉搜索树类似，只是将与单个关键字的比较换为与多个关键字的比较。从某个结点的比较看，书中给出的方法是顺序查找，如果 t 较大的话，二分查找会更有效率。
创建操作很简单，只是创建一个空的跟结点。
插入操作不能简单的插入新的叶结点，在遇到满的结点时要将结点分裂为两个结点，以保证插入新元素后仍然是合法的B树。
从B树中删除关键字
从B树中删除关键字非常复杂，复杂到书里都不愿意给出代码，只给了思路和分析。
B树的删除操作性能也很高，O(h) 次磁盘操作，O(th) 的 CPU 时间，同插入操作一样高效。
网友评论