9.2.2B树和B+树 ·B树：每个结点n个关键字，n+1个指针 m阶B树除根和叶子外，每个结点子树在m/2,m] ·B+树：每个结点n个关键字，n个指针 m阶B+树除根和叶子外，每个结点子树在[m/2,m 9.2.3键树 ·键树、数字查找树(Digital search trees). 一结点不是关键字，而是关键字中的一个字符，从根到叶 子结点的路径（根、叶子本身除外）才是关键字 ·键树的存储（双链树) 一采用孩子-兄弟的存储方法。 ypb@ustc.edu.cn 11 中国科学技术大学
ypb@ustc.edu.cn 11 中国科学技术大学 9.2.2 B树和B+树 • B树：每个结点n个关键字，n+1个指针 m阶B树除根和叶子外，每个结点子树在[m/2,m] • B+树:每个结点n个关键字，n个指针 m阶B+ 树除根和叶子外，每个结点子树在[m/2,m] 9.2.3 键树 • 键树、数字查找树（Digitalsearch trees） – 结点不是关键字，而是关键字中的一个字符,从根到叶 子结点的路径（根、叶子本身除外）才是关键字 • 键树的存储（双链树） – 采用孩子－兄弟的存储方法
四阶B树 5 44o58 2欧6223 30☑f8Fo2o 向包前的包包向包包的回白包回回位 ypb@ustc.edu.cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 四阶B树 ● 24 ● ● 15 ● 20 ● ● 34 ● 40 ● 58 ● ● 10 ● 12 ● ● 16 ● ● 21 ● 23 ● ● 30 ● 31 ● ● 38 ● ● 47 ● ● 50 ● 52 ● 60 ● F F F F F F F F F F F F F F F F F F F