§9.32B树 1概念 B树是一种完全平衡的多阶查找树,主要是作为磁盘文件的索引组织,用于 外部查找。 ■基本想法是增大结点来降低树高,减少访问外存的次数 棵m阶B树,每个结点最多有m个孩子,m一般为50-2000 例如,1棵1001阶B树,3层即可包含10亿以上的Keys,当根结点置于内存 时,查找任一Key至多只要访问2次外存。 1000 1个结点 1000个关键字 1001 10001000 1000 1001个结点 1,001,000个关键字 量B 1001 1000 1000 10011,002,001个结点 1,002,001,000个关键字1 § 9.3.2 B-树 1.概念 ◼ B-树是一种完全平衡的多阶查找树，主要是作为磁盘文件的索引组织，用于 外部查找。 ◼ 基本想法是增大结点来降低树高，减少访问外存的次数 一棵m阶B-树，每个结点最多有m个孩子，m一般为50－2000 例如，1棵1001阶B-树，3层即可包含10亿以上的Keys，当根结点置于内存 时，查找任一Key至多只要访问2次外存。 1000 1000 1000 1000 1000 1000 … 1001 … 1001 … 1001 1个结点 1000个关键字 1001个结点 1,001,000个关键字 1,002,001个结点 1,002,001,000个关键字