若B-树的阶数m=3,高度h=4,则关键码总 数至少为N=2「3/2141-1=15。 m值的选择 如果提高B-树的阶数m,可以减少树的高度 从而减少读入结点的次数,因而可减少读磁盘 的次数。 事实上,m受到内存可使用空间的限制。当m 很大超出内存工作区容量时,结点不能一次读 入到内存,增加了读盘次数,也增加了结点內 查找的难度
若B-树的阶数 m = 3，高度 h = 4，则关键码总 数至少为 N = 2 3 / 2 4-1-1 = 15。 m值的选择 如果提高B-树的阶数 m，可以减少树的高度， 从而减少读入结点的次数，因而可减少读磁盘 的次数。 事实上，m 受到内存可使用空间的限制。当m 很大超出内存工作区容量时，结点不能一次读 入到内存，增加了读盘次数，也增加了结点内 查找的难度
m值的选择:应使得在B-树中找到关键码x的 时间总量达到最小 这个时间由两部分组成 从磁盘中读入结点所用时间 在结点中查找x所用时间 根据定义,B-树的每个结点的大小都是固定的 结点内有m-1个索引项KDA,1≤i<m。 其中,K所占字节数为a,D和A所占字节数 为β,则结点大小近似为m(+2)个字节。读 入一个结点所用时间为 tseek t tlatency m(a+ 2B)tran=a+ bm
m值的选择：应使得在B-树中找到关键码x 的 时间总量达到最小。 这个时间由两部分组成： 从磁盘中读入结点所用时间 在结点中查找 x 所用时间 根据定义，B-树的每个结点的大小都是固定的， 结点内有 m-1 个索引项 (Ki , Di , Ai ), 1 i < m。 其中，Ki 所占字节数为，Di 和 Ai 所占字节数 为，则结点大小近似为 m(+2) 个字节。读 入一个结点所用时间为： t seek + t latency + m( + 2) t tran = a + bm
B-树的插入 B-树是从空树起,逐个插入关键码而生成的。 在B-树,每个非失败结点的关键码个数都在 T「m21-1,m-11 之间。 插入在某个吐结点开始。如果在关键码插入后 结点中的关键码个数超出了上界m-1,则结点 需要“分裂”,否则可以直接插入。 实现结点“分裂”的原则是 0设结点A中已经有m-1个关键码,当再插入 个关键码后结点中的状态为
B-树的插入 B-树是从空树起，逐个插入关键码而生成的。 在B-树，每个非失败结点的关键码个数都在 [ m/2 -1, m-1] 之间。 插入在某个叶结点开始。如果在关键码插入后 结点中的关键码个数超出了上界m-1，则结点 需要“分裂”，否则可以直接插入。 实现结点“分裂”的原则是： 设结点 A 中已经有 m-1 个关键码，当再插入 一个关键码后结点中的状态为
(m2A0,K1,A1,k2A2,……,KmAm) 其中K1<K#1,1≤i<m 0这时必须把结点p分裂成两个结点p和q, 它们包含的信息分别为 结点p: (m21-1,AnK1,A1, ,A「m21-134「m27 结点q: (m-「m2,m2bm2+,m+…,m 位于中间的关键码Km与指向新结点q的 指针形成一个二元组(Kmq),插入到这 两个结点的双亲结点中去
( m, A0 , K1 , A1 , K2 , A2 , ……, Km, Am) 其中 Ki < Ki+1, 1 i < m 这时必须把结点 p 分裂成两个结点 p 和 q， 它们包含的信息分别为： 结点 p： ( m/2 -1, A0 , K1 , A1 , ……, Km/2 -1 , Am/2 -1 ) 结点 q： (m - m/2, Am/2 , Km/2+1, Am/2+1, ……, Km, Am) 位于中间的关键码 Km/2与指向新结点 q 的 指针形成一个二元组 ( Km/2 , q )，插入到这 两个结点的双亲结点中去
n Po K1 P1 K2 p2 53 75 n Po k1 P1 K2 P2 K3 P3 53 751139 n Po K1 P 75 n po K1 p n Po K1 p1 p1 53 139 结点“分裂”的示
结点“分裂”的示 例