This morning I stumbled upon a B-Tree Page API Example from Robert Sedgewick & Kevin Wayne (Algorithms 4/e).
Its in Java but can easily be transformed into C++:
public class Page<Key>
Page(boolean bottom) // create and open a page
void close() // close a page
void add(Key key) // add key into the (external) page
void add(Page p) // open p and add an entry into this
// (internal) page that associates
// the smallest key in p with p
boolean isExternal() // Is this page external?
boolean contains(Key key) // is key in the page?
Page next(Key key) // the subtree that could contain the key
boolean isFull() // has the page overflowed?
Page split() // move the highest-ranking half of the
// keys in the page to a new page
Iterable<Key> keys() // iterator for the keys on the page
- Is this useable as starting point for our Page API?
- What should be different for an R*Tree?
- Already answers some questions from my previous e-mail: Key(coordinates) should always be known.
For your information,