|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 07年DS的B树题目－－我的解答，大家帮忙看看，欢迎指正 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=56530) |
|
-- 作者：shuimu -- 发布时间：12/8/2007 11:59:00 AM -- 07年DS的B树题目－－我的解答，大家帮忙看看，欢迎指正 记得前段时间讨论过这个题目，我没找到链接，所以把我的解法贴出来， 请大家帮忙看看是否正确？ 假设一个数据文件每个记录对象需要占用128字节（其中关键码占用4字节），且所有记录均已按关键码有序地存储在主磁盘文件中。设磁盘页块大小为2048（=2K）字节，若主存中有12M空间可以用来存储索引结构，索引项中每一个地址指针占8字节。请简要回答以下问题（请写明你的计算过程）。 （1）使用B树索引，B树的阶m最多可以为多少？ 注：在B树中找到关键码的同时，应该可以得到其在主文件中的地址。 （2）4层m阶B树，最多可以索引多少字节的数据文件？ 注：独根B树算1层，空B树算0层；要求根据题目给出的数据，给出计算结果和具体的计算过程。 （3）给定12M的内容用于B树索引操作，而且尽量把B树的头几层放入内存（同一层结点要么全都放入内容，要么都在外层）。那么给定关键码，从根结点开始，通过B树查找到（2）小题中主数据文件的一个记录，最少几次访外？最多几次访外？ 解: (1) B树中每个结点除了存放关键码外, 还需存放子结点的地址指针以及该关键码所在的记录的主文件的地址指针, 设结点的关键码个数为k, 则 k*4+(k+1)*8+k*8 < =2K k<=102 从而m的阶最大为103 (2) m取(1)中计算得到的最大值103 4层103阶B树每一个结点的最大关键码数为102 所以最多可以索引的数据文件: (102+102*103+102*1032+102*1033)*128 B (3) 每个结点的存储空间为2K 102< 12 M/2 K <102*103 所以内存中只能存放根结点 最少访外1次, 通过内存中根结点直接得到主文件地址进行磁盘访问 最多访外4次(第2, 3,4层各一次,实际记录一次). |
|
-- 作者：daizw -- 发布时间：12/8/2007 10:26:00 PM -- (1)题目中所说的地址指针是指"索引项地址指针"抑或"主文件地址指针"? 书中的主文件地址指针是4B. 所以我觉得题意不清 (3)你似乎算错了,应该可以放两层的. |
|
-- 作者：tianqing4569 -- 发布时间：12/9/2007 11:49:00 PM -- 第三问算错了，是两层 |
|
-- 作者：shuimu -- 发布时间：12/10/2007 5:52:00 PM -- 谢谢！第３题是算错了！ |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
62.500ms |