Benedict created CASSANDRA-9769:
-----------------------------------
Summary: Improve BTree
Key: CASSANDRA-9769
URL: https://issues.apache.org/jira/browse/CASSANDRA-9769
Project: Cassandra
Issue Type: Improvement
Components: Core
Reporter: Benedict
Assignee: Benedict
Fix For: 3.0 beta 1
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)
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
