4 ms·
Datastructures for external memory
- mozumder 10y agoThe Intel 750 SSD definitely doesn't get 440k IOPS with a queue depth of 1. It's more like 10k IOPS at that queue depth. This basic assumption mistake really changes a lot of the numbers in the article.
- rawnlq 10y agoWhy aren't these data structures also good for main memory? Is the gap between L1/L2 cache vs main memory not large enough? (1ns vs 100ns)
- corysama 10y agoB-Trees are quite popular in-memory structures when focusing on performance. I expect the others could be adapted as well (and likely have been). A quick google turns up http://www.cs.cmu.edu/~chensm/papers/fpbtree.pdf http://www.cs.cmu.edu/~chensm/papers/fpbtree.pdf
- jules 10y agoThese data structures are good for main memory. I've implemented in-memory B-trees in C#, and they were 2x to 5x faster than .NET's built-in sorted maps. The built-in sorted maps also used 3x as much memory. Surprisingly, B-trees are better even for immutable collections, beating the built-in .NET immutable sorted map by 3x to 5x on updates. This is all with a straightforward implementation. Red-black trees and AVL trees should not be used any more in my opinion. They are much slower and in my opinion B-trees are easier to understand and implement. It is still customary for data structure courses to teach red-black trees and AVL trees, but they should teach B-trees instead.
- known 10y agoLet RDBMS take care of it
- gbrown_ 10y agoThis reminded me of BetrFS presented at FAST 15. It looks like there's a more up to date presentation online[1] where the delete performance issues have been fixed. [1] https://www.youtube.com/watch?v=fBt5NuNsoII https://www.youtube.com/watch?v=fBt5NuNsoII