HN Gopher Feed (2017-10-05) - page 1 of 10
Modern B-Tree Techniques (2011)
190 points by pointy_hathttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.219.726...
bootcat - 3 hours ago
Really good read ! Must read for people who like algorithms and
competitive programming !
cryptonector - 38 minutes ago
> 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 fieldsYes, 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.
makmanalp - 5 hours ago
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
graefe-2017-si...He also has a lot to say about locking in B-trees:
mistercow - 6 hours ago
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.
sctb - 5 hours ago
Thanks, we've updated the title!