[CASSANDRA-9471] Columns should be backed by a BTree, not an array

• Type: Improvement
• Status: Resolved
• Priority: Normal
• Resolution: Fixed
• Fix Version/s: 3.0 beta 1
• Assignee: Benedict Elliott Smith
• Reporter: Benedict Elliott Smith

Authors

Benedict Elliott Smith

Reviewers

Branimir Lambov

• Created: 25/May/15 08:10
• Updated: 16/Apr/19 09:31
• Resolved: 06/Aug/15 12:49

Description

Follow up to 8099.

We have pretty terrible lookup performance as the number of columns grows (linear). In at least one location, this results in quadratic performance.

We don't however want this structure to be either any more expensive to build, nor to store. Some small modifications to BTree will permit it to serve here, by permitting efficient lookup by index, and calculation of index for a given key.

Issue Links

• depends upon: CASSANDRA-8099 Refactor and modernize the storage engine