| This reading list will cover a lot the current generation of b-tree techniques, but not the cutting-edge stuff (e.g. Tokutek): * Ubiquitous B-Tree (Douglas Comer): http://doi.acm.org/10.1145/356770.356776 [A good review of the state-of-the-art in 1979] * Prefix B-trees (Bayer, Rudolf and Unterauer, Karl): http://doi.acm.org/10.1145/320521.320530 [This paper introduces the idea of what I'm used to calling suffix compression -- the internal page pointers in a B-tree don't need to store the entire key, just enough of it to uniquely identify the node compared to its neighbor. This can be a very useful optimization for some use cases. The idea of reassembling a key as you seek down the tree is cool, but I don't think anyone does it in practice.] * B-tree indexes, interpolation search, and skew (Goetz Graefe): http://doi.acm.org/10.1145/1140402.1140409 [A lot of interesting ideas around doing search inside of a node, including cache awareness. Interpolated search looks very interesting, but I was never able to get it to go faster than binary search. That could have been my fault though.] * A survey of B-tree locking techniques (Goetz Graefe): http://doi.acm.org/10.1145/1806907.1806908 [I really like Graefe's database survey papers. They are easy to read and practical/implementation focused. This one discusses a lot of important concepts: the difference between latches and locks, latch coupling, range locks and increment locks.] |