Details
-
Improvement
-
Status: Resolved
-
Normal
-
Resolution: Fixed
-
None
-
None
Description
Split out from CASSANDRA-9471, after discussion there. This patch contains all of the btree centric changes, as well as some minimally invasive replacement of TreeMap around the codebase.
- Introduces "indexing" to the BTree class, permitting lookup by positional index, and binarySearch semantics (so inequality lookups yield the position a binarySearch of the equivalent array would)
- The size modulo remainder of a Leaf/Branch are flipped, so that a Branch has a spare slot at the end for an int[] index:
- if missing, this occupies at most 1 bit per entry in the set (often 1/32), if present, it occupies at most 2.5 bits, and typically around 1 bit. Sets with <= 32 items incur no cost.
- This index just contains the cumulative size of the tree preceding each branch key, rooted at the node in question
- The size modulo remainder of a Leaf/Branch are flipped, so that a Branch has a spare slot at the end for an int[] index:
- Reintroduces BTreeSet, with extra methods for accessing by index*, and simple implementations of missing NavigableMap methods using this new functionality
- Introduces a simple BTreeSet.Builder, and replaces all suitable uses of TreeMap in the codebase with a BTreeSet.Builder -> BTreeSet
- Rewrites btree.Cursor to make it far easier to understand, and to introduced IndexedSearchIterator, exposing the new indexing
- Reintroduces LongBTreeTest, with cleaned up more exhaustive coverage of iterator functionality, and new NavigableMap methods
This version further cleans up a few things, and switches to always indexing a btree, given the costs are fairly low (which permits eliminating quite a bit of code that would be required if the positions of items were not known, and providing just one iterator implementation)