3 ms·
"B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound." I am not an expert on file systems, but have you thought
by Someone 14y ago
"B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound."
I am not an expert on file systems, but have you thought about the following:
- using file names in disk blocks rather than file name hashes means fewer entries per disk block. That, in turn, changes the constant of your B-tree traversal.
- with variable-length keys, keeping your B-trees balanced is tricky, if not practically impossible.
EDIT: disadvantage of using hashes would be that you need to read the filename proper (with small hashes, you cannot ignore hash collisions). That would be an extra I/O. So I guess this would not be beneficial for small directories. Maybe you could start out by having in-block hashes amd filenames and only move the names to a separate block when you need a second block?
- cokernel_hacker 14y agoThe most common implementation technique that I know of is to include a small constant number (~4) bytes of the actual name next to the hash.
- Someone 14y agoI can see how that would help if your filenames are bin, dev, opt, usr, and var, but in the general case, I do not see how that beats having a longer hash (or a second, independent hash). Four bytes of the name will have less entropy than such data, and having part of the filename around will not help making sure that a matching hash implies a matching filename. Can you give explain this or give a name of a filesystem doing this?