关键码空间( key space)分解 不依赖于关键码的插入顺序 树的深度受到关键码精度的影响 ■最坏的情况下,深度等于存储关键码所需要的位数 例如,如果关键码是0到255之间的整数,那么关键码 的精度就是8个二进制位。 如果有两个关键码:10000001000001,它们的前面7位都 是相同的 所以直到第8次划分才能将这两个关键码分开 n这样的搜索树深度也为8,但这是最坏的情况 北京大学信息学院 @版权所有,转载或翻印必究 Page 6北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 关键码空间（key space）分解 ◼ 不依赖于关键码的插入顺序 ◼ 树的深度受到关键码精度的影响 ◼ 最坏的情况下，深度等于存储关键码所需要的位数 ◼ 例如，如果关键码是0到255之间的整数，那么关键码 的精度就是8个二进制位。 ◼ 如果有两个关键码：10000010和10000011，它们的前面7位都 是相同的 ◼ 所以直到第8次划分才能将这两个关键码分开 ◼ 这样的搜索树深度也为8，但这是最坏的情况