[ https://issues.apache.org/jira/browse/CASSANDRA-9769?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14620256#comment-14620256 ]
Benedict commented on CASSANDRA-9769: ------------------------------------- It may be worth considering renaming {{BTree}} -> {{RawBTree}} and {{BTreeSet}} -> {{BTree}}, since {{BTreeSet}} now also implements {{List}}, which is a bit confusing. Or perhaps {{BTreeSet}} -> {{BTreeListSet}}. Haven't done this for the moment, as it isn't super important, would involve a lot of unnecessary diffs for review, and it's always worth discussing nomenclature first. > 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)