5 ms·
When you're asked, during a job interview, which is the fasted lookup function, don't, as is very common, say, "a B-tree." Perfect hash tables always win, hands
by benihana 15y ago
When you're asked, during a job interview, which is the fasted lookup function, don't, as is very common, say, "a B-tree." Perfect hash tables always win, hands down.
Wait, saying a B-tree is the common answer?
- thurn 15y agoFurthermore, B-trees are designed for storing things that don't fit into primary memory. They are the right answer for things like file systems, I think almost every file system uses some variant of them.
- lallysingh 15y agoSurprisingly not: https://ext4.wiki.kernel.org/index.php/Frequently_Asked_Questions#History_of_ext2.2C_ext3.2C_and_ext4 https://ext4.wiki.kernel.org/index.php/Frequently_Asked_Ques... http://www.geeksofpune.in/drupal/files/8058778-ext34talk.pdf http://www.geeksofpune.in/drupal/files/8058778-ext34talk.pdf ext2,3 used an indirect-block tree structure. Ext4 uses an extents system which is nicer, but still not (AFAIK, I've only skimmed this part) a B tree.