Skip to content

Commit a61191e

Browse files
yaojingguoyaojingguo
committed
perf: replace LLRB-tree with btree in interval.Tree
Fixes #6465
1 parent d962689 commit a61191e

11 files changed

Lines changed: 2277 additions & 701 deletions

File tree

‎pkg/ccl/sqlccl/backup.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -138,7 +138,7 @@ func allRangeDescriptors(ctx context.Context, txn *client.Txn) ([]roachpb.RangeD
138138
// spansForAllTableIndexes returns non-overlapping spans for every index and
139139
// table passed in. They would normally overlap if any of them are interleaved.
140140
func spansForAllTableIndexes(tables []*sqlbase.TableDescriptor) []roachpb.Span {
141-
sstIntervalTree := interval.Tree{Overlapper: interval.Range.OverlapExclusive}
141+
sstIntervalTree := interval.Tree{Overlapper: interval.ExclusiveOverlapper}
142142
for _, table := range tables {
143143
for _, index := range table.AllNonDropIndexes() {
144144
if err := sstIntervalTree.Insert(intervalSpan(table.IndexSpan(index.ID)), false); err != nil {

‎pkg/storage/command_queue.go‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -139,8 +139,8 @@ func (c *cmd) String() string {
139139
// typically contain many spans, but are spatially disjoint.
140140
func NewCommandQueue(coveringOptimization bool) *CommandQueue {
141141
cq := &CommandQueue{
142-
reads: interval.Tree{Overlapper: interval.Range.OverlapExclusive},
143-
writes: interval.Tree{Overlapper: interval.Range.OverlapExclusive},
142+
reads: interval.NewTree(interval.ExclusiveOverlapper),
143+
writes: interval.NewTree(interval.ExclusiveOverlapper),
144144
wRg: interval.NewRangeTree(),
145145
rwRg: interval.NewRangeTree(),
146146
coveringOptimization: coveringOptimization,

‎pkg/util/cache/cache.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -496,7 +496,7 @@ func (ic *IntervalCache) MakeKey(start, end []byte) IntervalKey {
496496

497497
// Implementation of cacheStore interface.
498498
func (ic *IntervalCache) init() {
499-
ic.tree = interval.Tree{Overlapper: interval.Range.OverlapExclusive}
499+
ic.tree = interval.NewTree(interval.ExclusiveOverlapper)
500500
}
501501

502502
func (ic *IntervalCache) get(key interface{}) *Entry {

0 commit comments

Comments
 (0)