The Ubiquitous B-Tree (1979) [pdf] • Hacker News Board

Re: The Ubiquitous B-Tree (1979) [pdf]

#11

Post by flgr » Wed, Jul 01, 2015, 8:03 AM UTC

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:

See here: https://www.researchgate.net/profile/Florian_Gross/publicati....

Along those lines:

* CSS Trees: Pointerless b-Trees with a layout optimized for cache lines (http://www.vldb.org/conf/1999/P7.pdf)

* Intel & Oracle's fast architecture-sensitive tree search (combines huge pages, cache line blocking, and SIMD in an optimal layout): http://www.researchgate.net/profile/Jatin_Chhugani/publicati...

* Adaptive radix trees (http://codematch.muehe.org/~leis/papers/ART.pdf)

Re: The Ubiquitous B-Tree (1979) [pdf]

#12

Post by rizzin » Wed, Jul 01, 2015, 8:24 AM UTC

detrino wrote: post #9

rizzin wrote: post #7

Why does the root have only two children and not d, like every other non-leaf node?

Because when you split the root, it can only have 2 children.

I didn't understand your answer even after rereading about tree operations but I think I found out the actual reason why the root can have less than d children:

it is because of rebalancing after deletion. Underflows can go all the way up to the root so its children can borrow its indices. And when root has only one index (and two children) and another underflow occurs then its children combined with its index can form a new root decreasing the tree height by one.

Re: The Ubiquitous B-Tree (1979) [pdf]

#13

Post by bbrazil » Wed, Jul 01, 2015, 10:02 AM UTC

craigching wrote: post #2

Both times before this was posted it garnered 0 comments: https://news.ycombinator.com/item?id=4317545 https://news.ycombinator.com/item?id=7243568 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 :) To get the conversation started, a couple of years ago, I decided to write…

I did my final year project of my degree on B-Trees (Cache Conscious Optimisation of STL Data Structures).

The short version is that you want to tune to page size, inserts/reads tend to be faster than RB-Trees but deletes are slower. This was true across a variety of chips and cpu architectures.

Re: The Ubiquitous B-Tree (1979) [pdf]

#14

Post by [deleted] » Wed, Jul 01, 2015, 11:01 PM UTC

srean wrote: post #10

craigching wrote: post #2

Both times before this was posted it garnered 0 comments: https://news.ycombinator.com/item?id=4317545 https://news.ycombinator.com/item?id=7243568 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 :) To get the conversation started, a couple of years ago, I decided to write…

Then this library from Google would interest you https://code.google.com/p/cpp-btree/ It exposes the standard STL container interface. Although it was primarily intended to be used as a map or a set, if I remember correctly they also had b-tree backed large vectors that outperformed std:: vectors in random reads. I seem to have lost the url for that post/comment.

[deleted]