[CASSANDRA-13748] Search optimization with exponential search

• Type: Improvement
• Status: Open
• Priority: Low
• Resolution: Unresolved
• Fix Version/s: 5.x
• Component/s: Legacy/Core
• Labels: performance
• Assignee: Unassigned
• Reporter: Jay Zhuang
• Created: 07/Aug/17 21:58
• Updated: 07/Mar/23 10:54

Description

Exponential search has better performance than binary search to search sequential adjacent items (the items are close to each other). For example, with this implementation, it outperforms binary search to search 1st, 2nd, 4th, 5th item. It could be the case for multi-seek iterators. I think it worth investigating if switching to exponential search could improve the overall performance.

Issue Links

• relates to: CASSANDRA-9988 Introduce leaf-only iterator