[
https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15026807#comment-15026807
]
Branimir Lambov commented on CASSANDRA-9991:
--------------------------------------------
Thanks, I think the code is much easier to understand now.
Performance-wise, I still think you can improve significantly on the number of
costly comparisons if you switch to working with indices. You are currently
doing three passes over the tree using binary searches with the provided
comparator (and the second version increases that number). That can be reduced
that to just one {{findIndex}} pass, where the later stages of the processing
do integer searches (see {{BTree.findByIndex}}).
bq. About the random test - I don't think it's a good idea to create a random
unit tests. The fundamental attribute of unit test is its repeatability. Is
there any convention in Cassandra how to create a randomized fuzzy tests?
The test can have a fixed seed, and just be something that's large enough,
hopefully covering scenarios that we did not think of. For example,
{code}
@Test
public void randomizedTest()
{
Random rand = new Random(2);
SortedSet<Integer> data = new TreeSet<>();
for (int i = 0; i < 1000; ++i)
data.add(rand.nextInt());
Object[] btree = BTree.build(data, UpdateFunction.<Integer>noOp());
assertTrue(BTree.isWellFormed(btree, CMP));
assertTrue(Iterables.elementsEqual(data, BTree.iterable(btree)));
while (btree != BTree.empty())
{
int idx = rand.nextInt(BTree.size(btree));
Integer val = BTree.findByIndex(btree, idx);
assertTrue(data.remove(val));
Object[] next = BTreeRemoval.remove(btree, CMP, val);
assertTrue(next != btree);
assertTrue(BTree.isWellFormed(next, CMP));
assertTrue(Iterables.elementsEqual(data, BTree.iterable(next)));
btree = next;
}
}
{code}
which currently fails an {{isWellFormed}} test.
bq. Bottom up was messier
Thank you, I thought you probably already tried it and wanted to hear why it
didn't work out.
> Implement efficient btree removal
> ---------------------------------
>
> Key: CASSANDRA-9991
> URL: https://issues.apache.org/jira/browse/CASSANDRA-9991
> Project: Cassandra
> Issue Type: Sub-task
> Reporter: Benedict
> Labels: patch
> Fix For: 3.x
>
> Attachments: trunk-9991.txt, trunk-9991.txt-v2
>
>
> Currently removal is implemented as a reconstruction by filtering and
> iterator over the original btree. This could be much more efficient, editing
> just the necessary nodes.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
