硬盘文件系统为什么不用hash表而要用树形结构?

cdsfiui

哈希只需要查找一次就能找到位置，难道不适合外部排序和查找吗?
为什么硬盘文件系统总是要用到B+树之类的树形结构呢?

MMMIX

回复 1# cdsfiui


    主要是为了性能吧。

另外，用 hash 的话，普适、好用的 hash 函数也不好构造。再次另外，hash 查找一般情况下要比较常数次，而不是一次；最坏情况下是 N 次；但是 B+ 树可以保证最坏情况下是 log(N) 次比较。

windoze

回复 1# cdsfiui

谁告诉你说hash表只需查找一次的……

bruceteen

一个好的hash（仅限好的，差的就更不谈了），也就是平均统计性能比较好。
实时性差极了，而且还不耐数据攻击（故意碰撞）
另外，只有具体到某一个特定问题，加了无数条件限制后，才可以写出一个“好”hash，根本没有普遍适用的“好”hash。

bruceteen

一个好的hash（仅限好的，差的就更不谈了），也就是平均统计性能比较好。
实时性差极了，而且还不耐数据攻击（故意碰撞）
另外，只有具体到某一个特定问题，加了无数条件限制后，才可以写出一个“好”hash，根本没有普遍适用的“好”hash。