• Improvement
    • Status: Resolved
    • Normal
    • Resolution: Fixed
    • 3.0 alpha 1
    • None
    • None


      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
      • 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)




            benedict Benedict Elliott Smith
            benedict Benedict Elliott Smith
            Benedict Elliott Smith
            Branimir Lambov
            0 Vote for this issue
            4 Start watching this issue