结点分裂次数 存储效率分析 设关键码数为N(空指针N1),内部结点数为p N≥1+(m/21-1)(p-1) B树整个树结构关键码不重写, 每个关键码实质上是(关键码, 页块地址)的二元组, 最差情况下每插入一个结点都经过分裂(除第 其中的记录地址也称为“隐含指 个),即p1个结点都是分裂而来的,则每 插入一个关健码平均分裂结点个数为 N(m/21-1).N「m/21 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 2-3树隐含指针 13 B+树的存储效率实际上更高 ■B+树其实是多级索引形式 n[[2mc四[s 最下一层是所有关键码的全集 (18.1)(a,a2)关健码页内地址 因此可以把此层形成顺序链表 非叶层结点中的关键码不需要带 3..4)(30 隐含指针 m吗“m叫m 张铭帖编写 叔所有,轨圆即 大带管息张铭写权质有,成即盛究 假设一个主文件有N个记录,假设 个页块可以存m个(关键码,子结点 哥容被設矣從鷗古手妓骂擀 页块地址)二元对 假设B+树平均每个结点有0.75m个子 笑肉紧品员数 结点 充盈度为(140.5)/2=75% 智说助车盘结想是75%,则树结点 a因此B+树的高度为「opgo3sm B树的高度为「log0smN1 大带息理张铭写 质有,印究 1717 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 97 结点分裂次数 „ 设关键码数为N(空指针N+1)，内部结点数为p „ 即 „ 最差情况下每插入一个结点都经过分裂(除第 一个)，即p-1个结点都是分裂而来的，则每 插入一个关键码平均分裂结点个数为 N ≥+ − − 1 21 1 ( / )( ) ⎡ ⎤ m p ⎡ ⎤ p N m − ≤ − − 1 1 / 2 1 ⎡ ⎤ ⎡ ⎤ s p N N m Nm = − ≤ − − ⋅ ≤ − 1 1 2 1 1 (/ ) / 2 1 239 240 279 008 040 052 110 135 142 212 045 112 236 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 98 存储效率分析 „ B树整个树结构关键码不重写， „ 每个关键码实质上是（关键码， 页块地址）的二元组， „ 其中的记录地址也称为“隐含指 针” 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 99 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 2-3树隐含指针 关键码 页内地址 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 100 B+树的存储效率实际上更高 „ B+树其实是多级索引形式 „ 最下一层是所有关键码的全集， „ 因此可以把此层形成顺序链表 „ 非叶层结点中的关键码不需要带 隐含指针 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 101 „ 假设一个主文件有N个记录，假设一 个页块可以存m个(关键码，子结点 页块地址)二元对 „ 假设B+树平均每个结点有0.75m个子 结点 „ 充盈度为(1+0.5)/2 = 75％ „ 因此B+树的高度为 ⎡ ⎤ log0 75 . m N 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 102 „ 可以容纳m个(关键码，子结点页块指 针) ，假设关键码所占字节数与指针 相同 „ 可以容纳B树的(关键码，隐含指针，子 结点页块指针)最多为2m/3(B树为0.67m 阶)。 „ 假设B树充盈度也是75％，则B树结点 有0.5m个子结点 „ B树的高度为 ⎡log0 5. m N⎤