I am looking into B+-trees for some sparse array implementations, but little experience with b+-trees (or more advanced features). Do you have recommendation of code and papers to read besides the one already cited ?
[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.]
[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.]
[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.]
* 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.]