cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Benedict (JIRA)" <>
Subject [jira] [Commented] (CASSANDRA-9769) Improve BTree
Date Thu, 09 Jul 2015 12:12:05 GMT


Benedict commented on CASSANDRA-9769:

I pushed a number of small nit commits, which I've now force pushed to merge together, along
with a necessary change for passing {{LongBTreeTest.toArrayTest}} - I had not run it since
upgrading this test to cover all slices of btrees, and I had neither implemented toArray correctly
for subsets/sublists, nor at all for descending sets. These were relatively trivial to support,
so I've done so, to make the test happy.

> Improve BTree
> -------------
>                 Key: CASSANDRA-9769
>                 URL:
>             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
> * 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
> *** 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

View raw message