[
https://issues.apache.org/jira/browse/CASSANDRA-9988?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16102593#comment-16102593
]
Jay Zhuang commented on CASSANDRA-9988:
---------------------------------------
{quote}
However, these are iterators, and the expectation is that there will be
multiple seeks during the iterator's lifetime. I had assumed that your
searchFound and searchNotFound enumerated (searched for) a sequence of found /
not found keys. There should probably be such variants.
{quote}
Okay, I can add more tests for that. But I don't think expSearch would make
multiple-seeks within a leaf node better, as multiple seeks would make the
{{n}} even smaller. And even in general, here is an article comparing
binarySearch vs. exponentialSearch (galloping Search): [Beating the binary
search algorithm – interpolation search, galloping
search|http://blog.teamleadnet.com/2014/06/beating-binary-search-algorithm.html]
Gallop(exponentialSearch) is actually not as good as JAVA default API
{{Arrays.binarySearch}}:!http://3.bp.blogspot.com/-mPLIu6llPBY/U5JoP-6xivI/AAAAAAAABMU/D9N5mhLNbOk/s1600/SearchTime.png!
For consistency concern, binarySearch() is wildly used in BTree code:
[BTree.java|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/btree/BTree.java],
[NodeCursor.java|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/btree/NodeCursor.java],
[TreeCursor.java|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/btree/TreeCursor.java],
[NodeBuilder.java|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java],
[BTreeRemoval.java|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/btree/BTreeRemoval.java]
> Introduce leaf-only iterator
> ----------------------------
>
> Key: CASSANDRA-9988
> URL: https://issues.apache.org/jira/browse/CASSANDRA-9988
> Project: Cassandra
> Issue Type: Sub-task
> Reporter: Benedict
> Assignee: Jay Zhuang
> Priority: Minor
> Labels: patch
> Fix For: 4.0
>
> Attachments: 9988-data.png, 9988-result2.png, 9988-result3.png,
> 9988-result.png, 9988-test-result3.png, 9988-test-result-expsearch.xlsx,
> 9988-test-result-raw.png, 9988-test-result.xlsx, 9988-trunk-new.txt,
> 9988-trunk-new-update.txt, trunk-9988.txt
>
>
> In many cases we have small btrees, small enough to fit in a single leaf
> page. In this case it _may_ be more efficient to specialise our iterator.
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
