cassandra-commits mailing list archives

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

    [ https://issues.apache.org/jira/browse/CASSANDRA-9769?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14620400#comment-14620400
] 

Benedict edited comment on CASSANDRA-9769 at 7/9/15 12:12 PM:
--------------------------------------------------------------

I pushed a number of small nit commits (mostly comments), which I've now force pushed to merge
together (with each other), along with a necessary change for passing {{LongBTreeTest.toArrayTest}}

I had not run this test since upgrading it 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.


was (Author: benedict):
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: 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)

Mime
View raw message