[
https://issues.apache.org/jira/browse/CASSANDRA-9769?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14627855#comment-14627855
]
Branimir Lambov commented on CASSANDRA-9769:
--------------------------------------------
+1
[BTree.compare|https://github.com/apache/cassandra/commit/5e4c3190666f8e3e9fed5516eab32771ae66bf86#diff-4b911b7d0959c6219175e2349968f3cdR725]:
It's a bit simpler if you think what you want to return:
{code}
if (a == NEGATIVE_INFINITY || b == POSITIVE_INFINITY) // also true for a==b
\in {-inf, +inf}
return (a == b) ? 0 : -1;
if (a == POSITIVE_INFINITY || b == NEGATIVE_INFINITY)
return 1;
{code}
> 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)
