[
https://issues.apache.org/jira/browse/CASSANDRA-9988?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15117219#comment-15117219
]
Benedict commented on CASSANDRA-9988:
-------------------------------------
Hi Piotr,
Thanks for your patch. A few comments:
# It would be great to have just one Leaf iterator, so that we can benefit from
efficient method despatch, as there will be only two search iterator
implementations
# We could probably get uniformly better behaviour by implementing [exponential
search|https://en.wikipedia.org/wiki/Exponential_search] for the leaf iterator;
this would bring our total number of comparisons down from {{n lg n}} to {{n}}
when searching an approximately equal set of items, without harming our best
case complexity.
# It would be preferable to get numbers using JMH, and comparing a codebase
that only contains the full search iterator, versus one that contains both (and
performs searches that cross the boundaries, so it's unknown which will be
returned), as method despatch will potentially be harmed
> Introduce leaf-only iterator
> ----------------------------
>
> Key: CASSANDRA-9988
> URL: https://issues.apache.org/jira/browse/CASSANDRA-9988
> Project: Cassandra
> Issue Type: Sub-task
> Reporter: Benedict
> Priority: Minor
> Labels: patch
> Fix For: 3.x
>
> Attachments: 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.3.4#6332)
