B树 Monday, October 12, 2009

    今天在看Symbian 数据库相关资料的时候，提到了B树。下面就说说这个B树。

    什么是B树？B树就是满足下面三个条件的数据结构

1.  所有节点只能存储一个关键字；
2. 所有非叶子节点最多有两个子节点，也就是左节点，右节点
3. 非叶子节点的左节点的关键字小于该非叶子节点的关键字，右节点大于该非叶子节点的关键字

        大家都知道，B树也叫做搜索二叉树。它的搜索过程大体是这样的，从根节点开始，如果待搜索的关键字大于根节点的，就转入右节点比较，以此类推；如果等于根节点的关键字就算命中。

        对于一棵平衡的B树，也就是从根节点看左右节点数目差不多的B树，其搜索性能跟二分法查找差不多。但是B树在插入和删除节点方面的性能要优于二分法，B树在这方面通常只是常数级别的开销。

        值得注意的是B树的结构并不稳定。这表现为：

1. 经过多次插入、删除后，最差的结果是B树可能变成一个线性结构。这时搜索性能就变成线性的了！
2. 同样的关键字集合，由于选取了的不同的根节点可能有不同的结构。

        由此可见如何保持B树“平衡”是关键。这就衍生出了好多平衡算法。