讨论下腾讯实习笔试的填空题，磁盘块的

大家会填空题关于磁盘块的那题么？

文件F具有10000个记录，每个记录50字节，其中10字节表示文件键值，每个磁盘块大小为1000字节，指向磁盘块的指针占5字节，不允许记录跨越两个块。

1）建立简单hash索引，使用100个hash桶，则桶目录需要多少磁盘块？平均每个桶需要多少个磁盘块？

2）建立B+索引树，各磁盘块尽量装满，需要多少磁盘块存储索引？

懵逼

全部评论

推荐最新楼层

qw平常心

西北工业大学 Java

（1）如果为文件F建立简单hash索引，使用100个hash桶，则桶目录需要多少磁盘块？平均每个桶需要多少磁盘块？答：（1）1 （2）10000个记录/100个桶＝100个记录每桶，100个记录×50字节每记录/1000字节每块＝5块如果为文件F建立B+树索引，各磁盘块尽量装满，需要多少磁盘块存储索引？答：求秩D：5D+10(D+1)<=1000 => D=67 即每个叶节点能保存D-1=66个键值。所以叶节点数为?10000/66?＝152个。上一层的内节点同样有67个指针，是一个67叉的节点，?10000/67?＝3，?3/67?＝1 因此B+树的节点总数为152+3+1=156个。即需要156个磁盘块存储B+树索引。

点赞回复分享

发布于 2017-04-04 22:08

BBge

浙江大学 Java

第二题，先求秩X：5X+(10X+1) <= 1000 X = 67 那么每个叶节点能保存 67 -1 = 66个键值然后10000/66 < 152 152/66 < 3 3/66 <1 共需要152+3+1 = 156个磁盘块

点赞回复分享

发布于 2017-04-03 21:59

小度小度

南京大学 Java

死循环懵逼

点赞回复分享

发布于 2017-04-03 21:23

砰砰

上海科学技术职业学院 C++

一个硬盘块1000 解方程5D + 10(d+1)解得一个叶子结点（硬盘块）可以装67个指针，即66个值，所以需要叶子结点10000/66 = 152个块，上一层结点152/67 = 3,再上一层1/67 = 1，所以需要156个块

点赞回复分享

发布于 2017-04-03 21:57

东447

武汉工程大学 Java

加一个问题，把所有的数据算上，各占多少个磁盘块，画一张详细的图出来，再好不过了

点赞回复分享

发布于 2017-04-04 19:26

东447

武汉工程大学 Java

小白，不懂第二题的原理，能非常仔细地解释一下吗？为什么5d+10(d+1)＜1000 难道默认一个叶子节点占据一个数据块，为什么d+1，为什么求出来依旧d-1为最终叶子节点的key值?

点赞回复分享

发布于 2017-04-04 19:23

ATRuin

楼主

华南理工大学 Java

==你们会那个 #define A 3+5 #define B A*A 求 B*2 这个么。。不是 3+5*3+5*2=3+15+10=28么。。根本没这个答案，只有个128，看到有牛友直接猜测了这个是出题人打错了，是28的意思然后选了这个。我看这么不行就选了(3+5*3+5)*2=46 那个答案。。Orz，这题目还得猜出题人错误。。

点赞回复分享

发布于 2017-04-03 21:53

仙吖

University of Sydney Java

第二问怎么做，坐等解答

点赞回复分享

发布于 2017-04-03 21:48

虎山vvv

网易_引擎开发

第一问，5*100＜1000，1块，50*10000/(100*1000)=5块

点赞回复分享

发布于 2017-04-03 21:32