Alan Gutierrez

These were once the objectives for Strata, reflecting an early understanding of the project. I’m about to rewrite them, so I thought I’d put them somewhere, besides the wiki history.

Thus, the short-term objectives for Strata are as follows.

• Leaf nodes only to store references to file positions, not store the data itself.
• Branches also store only references to file positions, and hold a list of objects read from those file positions to use as keys.
• Thread-safe.
• File backed, paged.
• Supports efficent insertion and deletion, while maintaining the balance of the B-Tree.
• Equality comparison query.
• Compares byte buffer ranges, not objects.

Crazy thoughts included storing partial in the inner tiers on pages, but this presents a strange case where a partial key might not fit on a page, if the length of a key is unbounded.

What changed? For the first two points, only the way I’d state them. Since it’s now a given, I don’t know if I’d state them. There are also a few more devils in those two details, only the fields of interest may be cached for example.

“Equality comparison query”, meant that the only operator supported is the equality operator, which is also given, but that’s all you need to implement between, less than, greater than, etc. Probably could not see that then.

“Compares byte buffer ranges, not objects”, the meaning of this has escaped my memory.

The crazy thoughts are reflections on how to store the objects referenced by the B+Tree. There was a time when I thought that the objects might be stored in the pages of the tree.