Implementing ranged queries with B+trees and snapshot isolation

Question

I'm developing a new NoSQL database server product. Are there any papers on how to implement range queries on clustered B+ trees that uses snapshot isolation?

Answer 1

I have written a couple of B+tree implementations. For a range query you move a cursor to the key with the lower bound of the range, then "move right" till you reach the upper bound. A B+-link tree (which has left/right-pointers between the leaf nodes) makes this extremely simple.

I have, however, never implemented snapshot isolation. I think this strongly depends on your isolation algorithm. If you use shadow pages (where you create copies of the modified pages for each transaction) then you have to check if a shadow page exists before "moving right" along the leaf nodes.

Answer 2

You can add a hidden column to each row called "RowVersion". Whenever you update a row you insert a new row instead with the RowVersion updated to the current transaction number. When reading, you take that row that has the lowest version that is >= than your transaction number. You would also need some kind of cleanup task.

You can also store row version in a different location. It does not have to be in the same B-tree. You could hold them in RAM or on a temp database that gets recreated on server restart.