server/schedule/rangelist: could we use segment tree to optimize the complexity to O(logN) from O(N)?
Open
difficulty/medium
good first issue
type/enhancement
- Dominant language
- Go
- Stars
- 1.2k
- Forks
- 783
- Avg merge
- 5d 21h
- Merged PRs (30d)
- 36
Description
## Enhancement Task
Could we use [segment tree](https://en.wikipedia.org/wiki/Segment_tree) to optimize the complexity of range-list from O(N) to O(logN) , both write-and-read operators.
The related source-file:
[https://github.com/tikv/pd/blob/c8775b6176a03eb25cb1622fc46ba1d496872df7/server/schedule/rangelist/builder.go#L90-L114](https://github.com/tikv/pd/blob/c8775b6176a03eb25cb1622fc46ba1d496872df7/server/schedule/rangelist/builder.go#L90-L114)
Contributor guide
Assessment
This issue has not been assessed yet.