我们知道硬盘的读取速度是很慢的，那么如何实现文件系统才能让计算机更加高效呢？这时候就要引入B树的概念了。B树是平衡二叉树的推广形式，它的每个节点可以有很多的子节点。子节点的数量取决于扇区的大小。因为硬盘读取一个扇区的开销是最节省时间的。

下图展示了B树的样子，每个节点可以有多个子节点。

平衡树的应用

红黑树有着广泛的应用

Java：java.util.TreeMap, java.util.TreeSet

C++ STL：map, multimap, multiset

Linux：linux/rbtree.h

B树在文件系统中有着广泛的应用

NTFS  HFS  Ext3  JFS  ReiserFS  ORACLE  DB2  INGRES  SQL  PostgreSQL

算法5-3：B树,布布扣,bubuko.com

算法5-3：B树

原文：http://blog.csdn.net/caipeichao2/article/details/30089475