Modern B-Tree Techniques (2011)

by pointy_hat on 10/5/2017, 3:08:12 PM with 11 comments

  • by makmanalp on 10/5/2017, 5:54:34 PM

    For those who don't know, Goetz Graefe is sort of the patron saint of btrees. He recently won the Sigmod Codd innovations award for his contributions:

    https://sigmod.org/sigmod-awards/people/goetz-graefe-2017-si...

    He also has a lot to say about locking in B-trees:

    http://15721.courses.cs.cmu.edu/spring2016/papers/a16-graefe...

  • by cryptonector on 10/5/2017, 10:21:52 PM

    > Probably the strongest arguments for B-trees over hash indexes pertain to multi-field indexes and to nonuniform distributions of key values. A hash index on multiple fields requires search keys for all those fields such that a hash value can be calculated. A B-tree index, on the other hand, can efficiently support exact-match queries for a prefix of the index key, i.e., any number of leading index fields

    Yes, well, if none of the columns/fields in the index are sufficiently selective, then the ability to search a B-tree by prefix may not do you much good. Don't get me wrong though: I fully agree with all of the given reasons for B-tree superiority to hash tables.

    Although the newest storage technologies (particularly very fast byte-addressable NVMs) -- too new for TFA -- might well change things. When you have fast byte-addressable storage it will pay to not read pages, and hash tables may yet involve fewer accesses than B-trees in that case, though I suspect B-trees will successfully adapt anyways.

  • by hyc_symas on 10/6/2017, 12:42:39 AM

    Well, it's an interesting survey. I'm surprised at how much space it devoted to illustrating B-trees in the context of RDBMSs as a lot of the concepts there really had no specific connection to B-trees.

    So much space devoted to logging, locking and latches. All heavily used in the industry up till the last decade. All obsolete now. Not a single mention of immutable/persistent B-trees. Were there really no academic papers on the topic written in a time covered by this survey?

  • by mistercow on 10/5/2017, 4:50:38 PM

    This is from 2011, in case you missed that. I was confused by sentences like:

    >Flash memory, flash devices, and other solid state storage technology are about to change the memory hierarchy in computer systems in general and in data management in particular.

    until I looked up at the publication date.

  • by bootcat on 10/5/2017, 7:38:29 PM

    Really good read ! Must read for people who like algorithms and competitive programming !