CLRS-B树


很多数据库系统会使用B树来存储信息。因为B树的分支因子可以很大,即节点可以有很多孩子,这可以降低树的高度,以及查找任何一个关键字所需的磁盘存取次数
例如一棵高度为2分支因子为1001的B树,可以存储超过10亿个关键字,由于根结点已经在主存中,查找任何关键字都只需要2次磁盘存取

B树的定义

B树的高度和红黑树一样对数增长,但是对数的底数要大很多倍,这意味着磁盘访问次数少很多