http://blog.csdn.net/v_JULY_v/article/details/6530142/
磁盘的读写原理和效率磁盘上数据必须用一个三维地址唯一标示:柱面号、盘面号、块号(磁道上的盘块)。
访问某一具体信息由三部分时间组成:查找时间、等待时间、传输时间。
一棵m阶的B+树和m阶的B树的异同点在于：
1.有n棵子树的结点中含有n-1 个关键字； (此处颇有争议，B+树到底是与B 树n棵子树有n-1个关键字 保持一致，还是不一致：B树n棵子树的结点中含有n个关键字，待后续查证。暂先提供两个参考链接：①wikipedia http://en.wikipedia.org/wiki/B+_tree#Overview；②http://hedengcheng.com/?p=525。而下面B+树的图尚未最终确定是否有问题，请读者注意)
2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)
B*-tree是B+-tree的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，B*树中非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。
B*树分配新结点的概率比B+树要低，空间使用率更高。
红黑树和平衡二叉树区别如下： 1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。 2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。
红黑树和B树应用场景有何不同？
2者都是有序数据结构，可用作数据容器。 红黑树多用在内部排序，即全放在内存中的，微软STL的map和set的内部实现就是红黑树。 B树多用在内存里放不下，大部分数据存储在外存上时。因为B树层数少，因此可以确保每次操作，读取磁盘的次数尽可能的少。
在数据较小，可以完全放到内存中时，红黑树的时间复杂度比B树低。 反之，数据量较大，外存中占主要部分时，B树因其读磁盘次数少，而具有更快的速度。
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；
R树是一种能够有效进行高维空间搜索的数据结构，它已经被广泛应用在各种数据库及其相关的应用中。但R树的处理也具有局限性，它的最佳应用范围是处理2至6维的数据，更高维的存储会变得非常复杂，这样就不适用了。近年来，R树也出现了很多变体，R*树就是其中的一种。这些变体提升了R树的性能，感兴趣的读者可以参考相关文献。文章有任何错误，还望各位读者不吝赐教。本文完。
参考文献以及推荐阅读：
1. Organization and Maintenance of Large Ordered Indices
2. the ubiquitous B tree
3. http://en.wikipedia.org/wiki/Btree （给出了国外一些开源地址）
4. http://en.wikipedia.org/wiki/Btree#Technical_description
5. http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html（include C++ source code）
6. http://slady.net/操作。） 7. Guttman, A.; “R-trees: a dynamic index structure for spatial searching,” ACM, 1984, 14
