[
https://issues.apache.org/jira/browse/CASSANDRA-20594?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17947079#comment-17947079
]
Benedict Elliott Smith commented on CASSANDRA-20594:
----------------------------------------------------
I think an immutable augmented interval tree (based on our BTree) would be
fine, and something I have had on my infinite-length back burner for a little
while (and would also be useful for Accord)
We also have an interim option of improving the search time of
SearchableRangeList (which should be possible to bring to ~parity with
IntervalTree), and for which construction time is much lower, especially with
point-edits.
> Potential IntervalTree followup improvements
> --------------------------------------------
>
> Key: CASSANDRA-20594
> URL: https://issues.apache.org/jira/browse/CASSANDRA-20594
> Project: Apache Cassandra
> Issue Type: Improvement
> Components: Local/Compaction
> Reporter: Ariel Weisberg
> Priority: Normal
>
> The next step for improving {{IntervalTree}} is probably to replace it with a
> proper persistent tree rather than to keep hacking on the existing one
> yielding incremental improvements in the < 10x range. A persistent tree could
> yield 100-1000x improvements and allow us to stop worrying about IntervalTree
> performance indefinitely.
> Right now I think we have bought ourselves a ~5 years. Between the improved
> speed of the tree and increasing sstable size in leveled compaction (which is
> not a default!) to reduce the number of sstables an operator can probably
> limp along about that long.
> There are still some improvements that could be done to the current tree. The
> current tree has both a sorted array it always maintains to make updating the
> tree faster and then an actual interval tree with nodes. It might be possible
> to search the tree using just the sorted arrays which means we can discard
> the actual tree nodes and save a lot of the time spent building the tree
> nodes. Right now we pay the cost of updating the arrays on all forms of
> updates so the tree is just additional overhead.
> Continuing to improve the existing one is probably throwing good money after
> bad, but it’s tempting because implementing search on the arrays might
> actually be easy.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
