首页 > 代码库 > 算法5-3:B树

算法5-3:B树

我们知道硬盘的读取速度是很慢的,那么如何实现文件系统才能让计算机更加高效呢?这时候就要引入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