| （王道考研习题 | 您所在的位置：网站首页 › B-树的阶数是什么 › （王道考研习题 |
（王道考研习题
|
利用 B 树做文件索引时,若假设磁盘页块的大小是 4 000 B,指示磁盘地址的指针需要 5 B。现有 20 000 000 个记录构成的文件,每个记录为 200 B,其中包括关键字 5 B。
试问再这个采用B树作索引的文件中，B数的阶数应为多少？假定文件数据部分未按关键字有序排列，则索引部分需要占用多少磁盘块？
王道习题关于这道题的解析有视频也有文字版解析，先贴出王道的解析，个人认为解析能看懂但有些地方讲的不是很清晰，然后贴出我自己结合答案的理解。（有稍许与王道不同的地方） 王道解析
一、B树的阶数？
1.前提知识
B树中一个结点的大小不能超过一个磁盘页块的大小一个结点的内容包括：结点中的关键字+指向每一个关键字的指针+结点的子树指针+2B（一个整数，保存实际关键字个数）
2.求阶数
利用第一个前提知识：首先假设B树的阶数为m 则一个结点最大占用的空间： m-1个关键字+m-1个关键字指针+m个子树指针 
最终式子为：5（m-1）+5（m-1）+5m+2≤4000 求出m≤267 提示：题目表明一个指针需要5B，一个关键字5B.一个磁盘页块4000B 二、索引占用多少磁盘块用B树做文件索引时，构成文件的记录也是需要存放在磁盘页块中的，每个记录200B。 则一个磁盘页块可以存放4000/200=20个记录。 那么20000000个记录共需要多少个磁盘块？ 需要20000000/20=1000000个磁盘块。 B树的一个关键字就对应一个磁盘块，所以1000000个磁盘块就是1000000个关键字。 索引占用的磁盘块就转换成了： 一个阶数为267，关键字为1000000的B树有多少个结点? 注解：上面的前提知识里提到过，在存放B数索引时，一个磁盘块里存放一个结点。 接下来就简单多了: ①一个结点最多266个关键字 则结点最少为：1000000/266（向上取整，不然不够）≈2760 ②一个结点最少133个关键字（除了根节点之外） （10000-1）/133≈7518.7 这里我个人觉得应该这么理解最终的7519： 除了根节点之外的结点需要7518个磁盘块。 加上根节点单独一个磁盘块，共7519个磁盘块。 但多了k个关键字没地方放， 但此时不能单独把k个关键字作为一个结点（k |
【本文地址】
公司简介
联系我们