Switch from number based interval references to key based

[tomijaga]

Problem

Currently, when we scan an index we represent the entries returned from the scan as two numbers - the start and end index of the first and last key in the list of entries. The index is the ordered position of the key in the b-tree.
However, this could lead to incorrect results when executing queries while an entry in the database is updated during the query execution.
For instance, if we scan an index and it returns a an interval of (0, 5). If a new entry with the smallest key is inserted into the index (b-tree), it will be inserted at index 0 and as a result shift the results of our scan to (1, 6).

[tomijaga]

We are currently using the number intervals in the db but the more important fix is updating this in the b-tree implementations.
The b-trees use a similar system to reference entries in their iterators. They store the leaf node they are iterating over and the index of the current entry.
This leads to incorrect reads from the iterators when insert or delete operations are run sequence.
An example, i've noticed recently is reading from the iterator created from a b-tree scan and deleting the entry returned on every read. This creates a situation where we delete every 2nd entry from the first read in the iterator instead of deleting every consecutive entry in the iterator. This error continues to delete entries past the range included in the iterator which is very dangerous. The way it it happens is consider a read with a reference to position 0 in the leaf node. Once we read the value at position 0 in the iterator it is incremented to position 1 as the that's expected to be the position of the next read. However, once we delete the entry at position 0, the list of entries in the b-tree is shifted to the left and the next element to read will be at position 0 instead of position 1, leading us skip this entry and return the 2nd next entry.