GOPHERSPACE.DE - P H O X Y
gophering on hngopher.com
HN Gopher Feed (2017-10-05) - page 1 of 10
 
___________________________________________________________________
Modern B-Tree Techniques (2011)
190 points by pointy_hat
http://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
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...
 
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!