[ 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: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org