?

转：http://blog.csdn.net/v_JULY_v/article/details/6530142

作者： July 、weedge、 Frankie 。编程艺术室出品。

说明：本文从 B 树开始谈起，然后论述 B+树、B* 树，最后谈到 R 树。其中 B 树、 B+ 树及B*树部分由weedge完成， R 树部分由 Frankie 完成，全文最终由 July 统稿修订完成。

出处：http://blog.csdn.net/v_JULY_v ? 。

?

第一节、 B 树、 B+ 树、B*树

1. 前言：

动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树 (Red-Black Tree )，B-tree/B⁺ -tree/ B^* -tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O (log₂N ) 与树的深度相关，那么降低树的深度自然会提高查找效率。

但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下 （为什么会出现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树 结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

也 就是说，因为磁盘的操作费时费资源，如果过于频繁的多次查找势必效率低下。那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？根据磁盘查找存取的次 数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，那么是不是便能有效减少磁盘查找存取的次数呢？那这种有效的 树结构是一种怎样的树呢？

这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发，自然就想到平衡多路查找树结构，也就是这篇文章所要阐述的第一个主题B~tree， 即B树结构(后面，我们将看到，B树的各种操作能使B树保持较低的高度，从而达到有效避免磁盘过于频繁的查找存取操作，从而有效提高查找效率)。

B-tree（B-tree树即B树 ，B即Balanced，平衡的意思）这棵神奇的树是在 Rudolf Bayer ,?Edward M. McCreight (1970) 写的一篇论文《 Organization and Maintenance of Large Ordered Indices 》中首次提出的（ wikipedia 中： http://en.wikipedia.org/wiki/B-tree ，阐述了 B-tree 名字来源以及相关的开源地址）。

在开始介绍 B~tree