Both times before this was posted it garnered 0 comments:<p><a href="https://news.ycombinator.com/item?id=4317545" rel="nofollow">https://news.ycombinator.com/item?id=4317545</a><p><a href="https://news.ycombinator.com/item?id=7243568" rel="nofollow">https://news.ycombinator.com/item?id=7243568</a><p>When I read this I immediately recognized it as a PDF that I have in GoodReader (where I store all my technical PDFs). So I'm curious if it will start a good conversation about b-trees this time :)<p>To get the conversation started, a couple of years ago, I decided to write a b-tree data structure to refresh my skills a bit. I wrote it in C since I've been doing a lot of Java the last 10 years or so. I only got as far as an in-memory b-tree and had started working on getting it stored to disk before I abandoned the project (think I was working on it during Christmas holidays and the holiday ended).<p>I subsequently read that in-memory b-trees can actually outperform other tree data structures like rb-trees due to cache coherency. I never bothered to performance test my b-tree vs. an rb-tree I also wrote for fun.<p>Anyway, that's my story about b-trees!
If you are interested in an overview of B-Trees, similar data structures, and how well they work on modern hardware, you may also find the survey bit of my master thesis interesting:<p>See here: <a href="https://www.researchgate.net/profile/Florian_Gross/publicati.." rel="nofollow">https://www.researchgate.net/profile/Florian_Gross/publicati...</a>.<p>Along those lines:<p>* CSS Trees: Pointerless b-Trees with a layout optimized for cache lines (<a href="http://www.vldb.org/conf/1999/P7.pdf" rel="nofollow">http://www.vldb.org/conf/1999/P7.pdf</a>)<p>* Intel & Oracle's fast architecture-sensitive tree search (combines huge pages, cache line blocking, and SIMD in an optimal layout): <a href="http://www.researchgate.net/profile/Jatin_Chhugani/publication/221213860_FAST_fast_architecture_sensitive_tree_search_on_modern_CPUs_and_GPUs/links/0c96051f5d2990770d000000.pdf" rel="nofollow">http://www.researchgate.net/profile/Jatin_Chhugani/publicati...</a><p>* Adaptive radix trees (<a href="http://codematch.muehe.org/~leis/papers/ART.pdf" rel="nofollow">http://codematch.muehe.org/~leis/papers/ART.pdf</a>)
A lucid, enjoyable paper that allowed me to write a very fast B-Tree implementation in nascent ANSI C back in the day. Comer's books always struck just the right balance between scholarly completeness and clarity, at least to me.