Repository: tikv/pd
Pull request #5608 (2022-10-18 07:18:26)

pkg: support generic for btree
Signed-off-by: Ryan Leung <rleungx@gmail.com>

<!--
Thank you for working on PD! Please read PD's [CONTRIBUTING](https://github.com/tikv/pd/blob/master/CONTRIBUTING.md) document **BEFORE** filing this PR.
PR Title Format:
1. pkg [, pkg2, pkg3]: what's changed
2. *: what's changed
-->

### What problem does this PR solve?

<!--

Please create an issue first to describe the problem.
There MUST be one line starting with "Issue Number:  " and 
linking the relevant issues via the "close" or "ref".
For more info, check https://github.com/tikv/pd/blob/master/CONTRIBUTING.md#linking-issues.

-->
Issue Number: Ref #5648 #5606.

### What is changed and how does it work?
```
cd pkg/btree
go test -bench . -benchmem -count 5 > master/generic.txt
benchstat master.txt generic.txt
```
```
name                                 old time/op    new time/op    delta
Insert-8                                138ns ± 1%     106ns ± 0%   -23.06%  (p=0.008 n=5+5)
Seek-8                                  113ns ± 0%      74ns ± 1%   -34.79%  (p=0.008 n=5+5)
DeleteInsert-8                          294ns ± 1%     227ns ± 1%   -23.05%  (p=0.008 n=5+5)
DeleteInsertCloneOnce-8                 295ns ± 2%     228ns ± 1%   -22.85%  (p=0.008 n=5+5)
DeleteInsertCloneEachTime-8            1.18µs ± 1%    0.72µs ± 2%   -39.07%  (p=0.008 n=5+5)
Delete-8                                159ns ± 1%     120ns ± 1%   -24.72%  (p=0.008 n=5+5)
Get-8                                   104ns ± 1%      68ns ± 1%   -34.42%  (p=0.008 n=5+5)
GetCloneEachTime-8                      152ns ± 1%     114ns ± 1%   -25.00%  (p=0.008 n=5+5)
Ascend-8                               39.9µs ± 0%    31.1µs ± 0%   -21.98%  (p=0.008 n=5+5)
Descend-8                              38.9µs ± 1%    30.1µs ± 0%   -22.65%  (p=0.008 n=5+5)
AscendRange-8                          71.7µs ± 0%    49.8µs ± 0%   -30.57%  (p=0.008 n=5+5)
DescendRange-8                         93.0µs ± 0%    62.0µs ± 1%   -33.27%  (p=0.008 n=5+5)
AscendGreaterOrEqual-8                 52.3µs ± 1%    39.3µs ± 1%   -24.91%  (p=0.008 n=5+5)
DescendLessOrEqual-8                   74.5µs ± 0%    51.4µs ± 1%   -30.99%  (p=0.008 n=5+5)
DeleteAndRestore/CopyBigFreeList-8     4.87ms ± 0%    3.70ms ± 0%   -24.11%  (p=0.008 n=5+5)
DeleteAndRestore/Copy-8                4.99ms ± 0%    3.72ms ± 0%   -25.36%  (p=0.016 n=4+5)
DeleteAndRestore/ClearBigFreelist-8    2.45ms ± 0%    1.85ms ± 0%   -24.78%  (p=0.016 n=5+4)
DeleteAndRestore/Clear-8               2.58ms ± 2%    1.87ms ± 0%   -27.24%  (p=0.008 n=5+5)

name                                 old alloc/op   new alloc/op   delta
Insert-8                                37.0B ± 0%     19.0B ± 0%      ~     (p=0.079 n=4+5)
Seek-8                                  7.00B ± 0%     0.00B       -100.00%  (p=0.008 n=5+5)
DeleteInsert-8                          0.00B          0.00B           ~     (all equal)
DeleteInsertCloneOnce-8                 0.00B          0.00B           ~     (all equal)
DeleteInsertCloneEachTime-8            3.61kB ± 1%    2.53kB ± 1%   -29.94%  (p=0.008 n=5+5)
Delete-8                                0.00B          0.00B           ~     (all equal)
Get-8                                   0.00B          0.00B           ~     (all equal)
GetCloneEachTime-8                      48.0B ± 0%     48.0B ± 0%      ~     (all equal)
Ascend-8                                0.00B          0.00B           ~     (all equal)
Descend-8                               0.00B          0.00B           ~     (all equal)
AscendRange-8                           0.00B          0.00B           ~     (all equal)
DescendRange-8                          0.00B          0.00B           ~     (all equal)
AscendGreaterOrEqual-8                  0.00B          0.00B           ~     (all equal)
DescendLessOrEqual-8                    0.00B          0.00B           ~     (all equal)
DeleteAndRestore/CopyBigFreeList-8      275kB ± 0%     143kB ± 0%   -47.94%  (p=0.008 n=5+5)
DeleteAndRestore/Copy-8                 884kB ± 0%     466kB ± 0%   -47.30%  (p=0.008 n=5+5)
DeleteAndRestore/ClearBigFreelist-8    1.30kB ± 0%    0.86kB ± 0%   -33.38%  (p=0.008 n=5+5)
DeleteAndRestore/Clear-8                562kB ± 0%     299kB ± 0%   -46.82%  (p=0.008 n=5+5)

name                                 old allocs/op  new allocs/op  delta
Insert-8                                 0.00           0.00           ~     (all equal)
Seek-8                                   0.00           0.00           ~     (all equal)
DeleteInsert-8                           0.00           0.00           ~     (all equal)
DeleteInsertCloneOnce-8                  0.00           0.00           ~     (all equal)
DeleteInsertCloneEachTime-8              13.0 ± 0%      13.0 ± 0%      ~     (all equal)
Delete-8                                 0.00           0.00           ~     (all equal)
Get-8                                    0.00           0.00           ~     (all equal)
GetCloneEachTime-8                       3.00 ± 0%      3.00 ± 0%      ~     (all equal)
Ascend-8                                 0.00           0.00           ~     (all equal)
Descend-8                                0.00           0.00           ~     (all equal)
AscendRange-8                            0.00           0.00           ~     (all equal)
DescendRange-8                           0.00           0.00           ~     (all equal)
AscendGreaterOrEqual-8                   0.00           0.00           ~     (all equal)
DescendLessOrEqual-8                     0.00           0.00           ~     (all equal)
DeleteAndRestore/CopyBigFreeList-8       15.0 ± 0%      14.0 ± 0%    -6.67%  (p=0.008 n=5+5)
DeleteAndRestore/Copy-8                 1.19k ± 0%     1.19k ± 0%      ~     (all equal)
DeleteAndRestore/ClearBigFreelist-8      5.00 ± 0%      2.00 ± 0%   -60.00%  (p=0.008 n=5+5)
DeleteAndRestore/Clear-8                1.08k ± 0%     1.08k ± 0%    -0.09%  (p=0.008 n=5+5)
```
<!--

You could use the "commit message" code block to add more description to the final commit message.
For more info, check https://github.com/tikv/pd/blob/master/CONTRIBUTING.md#format-of-the-commit-message.

-->

```commit-message
```

### Check List

<!-- Remove the items that are not applicable. -->

Tests

<!-- At least one of these tests must be included. -->

- Unit test

### Release note

<!-- A bugfix or a new feature needs a release note. If there is no need release note, just uncomment the below line. -->

```release-note
None
```


ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: [REVIEW NOTIFICATION]

This pull request has not been approved.


To complete the [pull request process](https://book.prow.tidb.net/#/en/workflows/pr), please ask the reviewers in the [list](https://prow.tidb.net/tichi/repos/tikv/pd/pulls/5608/owners) to review by filling `/cc @reviewer` in the comment.
After your PR has acquired the required number of LGTMs, you can assign this pull request to the committer in the [list](https://prow.tidb.net/tichi/repos/tikv/pd/pulls/5608/owners) by filling  `/assign @committer` in the comment to help you merge this pull request.

The full list of commands accepted by this bot can be found [here](https://prow.tidb.net/command-help?repo=tikv%2Fpd).

<details>

Reviewer can indicate their review by submitting an approval review.
Reviewer can cancel approval by submitting a request changes review.
</details>

<!--Review Notification Identifier-->
codecov[bot]: # [Codecov](https://codecov.io/gh/tikv/pd/pull/5608?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv) Report
Base: **75.74**% // Head: **75.67**% // Decreases project coverage by **`-0.06%`** :warning:
> Coverage data is based on head [(`2c078e0`)](https://codecov.io/gh/tikv/pd/pull/5608?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv) compared to base [(`bc2019e`)](https://codecov.io/gh/tikv/pd/commit/bc2019e0c4a0eea1a9559f03a2f9de88511f793e?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv).
> Patch coverage: 76.86% of modified lines in pull request are covered.

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master    #5608      +/-   ##
==========================================
- Coverage   75.74%   75.67%   -0.07%     
==========================================
  Files         326      326              
  Lines       32251    32305      +54     
==========================================
+ Hits        24427    24446      +19     
- Misses       5722     5755      +33     
- Partials     2102     2104       +2     
```

| Flag | Coverage Δ | |
|---|---|---|
| unittests | `75.67% <76.86%> (-0.07%)` | :arrow_down: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/tikv/pd/pull/5608?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv) | Coverage Δ | |
|---|---|---|
| [pkg/btree/btree\_generic.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-cGtnL2J0cmVlL2J0cmVlX2dlbmVyaWMuZ28=) | `82.88% <75.78%> (ø)` | |
| [pkg/rangetree/range\_tree.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-cGtnL3JhbmdldHJlZS9yYW5nZV90cmVlLmdv) | `98.36% <100.00%> (+0.05%)` | :arrow_up: |
| [pkg/dashboard/keyvisual/input/core.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-cGtnL2Rhc2hib2FyZC9rZXl2aXN1YWwvaW5wdXQvY29yZS5nbw==) | `0.00% <0.00%> (-33.34%)` | :arrow_down: |
| [server/storage/endpoint/rule.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3N0b3JhZ2UvZW5kcG9pbnQvcnVsZS5nbw==) | `83.33% <0.00%> (-11.12%)` | :arrow_down: |
| [pkg/metricutil/metricutil.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-cGtnL21ldHJpY3V0aWwvbWV0cmljdXRpbC5nbw==) | `82.75% <0.00%> (-10.35%)` | :arrow_down: |
| [server/id/id.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL2lkL2lkLmdv) | `83.05% <0.00%> (-6.78%)` | :arrow_down: |
| [server/tso/local\_allocator.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3Rzby9sb2NhbF9hbGxvY2F0b3IuZ28=) | `64.86% <0.00%> (-6.76%)` | :arrow_down: |
| [server/storage/storage.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3N0b3JhZ2Uvc3RvcmFnZS5nbw==) | `67.30% <0.00%> (-3.85%)` | :arrow_down: |
| [server/schedule/labeler/labeler.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3NjaGVkdWxlL2xhYmVsZXIvbGFiZWxlci5nbw==) | `76.77% <0.00%> (-2.59%)` | :arrow_down: |
| [server/storage/endpoint/meta.go](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3N0b3JhZ2UvZW5kcG9pbnQvbWV0YS5nbw==) | `61.36% <0.00%> (-2.28%)` | :arrow_down: |
| ... and [26 more](https://codecov.io/gh/tikv/pd/pull/5608/diff?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv) | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/tikv/pd/pull/5608?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv).

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

rleungx: > need to delete `pkg/rangetree`?

Yes, it has already been deleted.
rleungx: /merge
ti-chi-bot: @rleungx: It seems you want to merge this PR, I will help you trigger all the tests:

/run-all-tests


<details>

Instructions for interacting with me using PR comments are available [here](https://prow.tidb.net/command-help).  If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.
</details>
ti-chi-bot: This pull request has been accepted and is ready to merge. <details>Commit hash: 2aefabc40ff60e9abdf90d5c476c17ad65cc9b04</details>
ti-chi-bot: @rleungx: Your PR was out of date, I have automatically updated it for you.

At the same time I will also trigger all tests for you:

/run-all-tests

If the CI test fails, you just re-trigger the test that failed and the bot will merge the PR for you after the CI passes.


<details>

Instructions for interacting with me using PR comments are available [here](https://prow.tidb.net/command-help).  If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.
</details>
ti-chi-bot: @rleungx: Your PR was out of date, I have automatically updated it for you.

At the same time I will also trigger all tests for you:

/run-all-tests

If the CI test fails, you just re-trigger the test that failed and the bot will merge the PR for you after the CI passes.


<details>

Instructions for interacting with me using PR comments are available [here](https://prow.tidb.net/command-help).  If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.
</details>

Patch:
diff --git a/pkg/btree/.travis.yml b/pkg/btree/.travis.yml
deleted file mode 100644
index 4f2ee4d97..000000000
--- a/pkg/btree/.travis.yml
+++ /dev/null
@@ -1,1 +0,0 @@
-language: go
diff --git a/pkg/btree/LICENSE b/pkg/btree/LICENSE
deleted file mode 100644
index d64569567..000000000
--- a/pkg/btree/LICENSE
+++ /dev/null
@@ -1,202 +0,0 @@
-
-                                 Apache License
-                           Version 2.0, January 2004
-                        http://www.apache.org/licenses/
-
-   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
-
-   1. Definitions.
-
-      "License" shall mean the terms and conditions for use, reproduction,
-      and distribution as defined by Sections 1 through 9 of this document.
-
-      "Licensor" shall mean the copyright owner or entity authorized by
-      the copyright owner that is granting the License.
-
-      "Legal Entity" shall mean the union of the acting entity and all
-      other entities that control, are controlled by, or are under common
-      control with that entity. For the purposes of this definition,
-      "control" means (i) the power, direct or indirect, to cause the
-      direction or management of such entity, whether by contract or
-      otherwise, or (ii) ownership of fifty percent (50%) or more of the
-      outstanding shares, or (iii) beneficial ownership of such entity.
-
-      "You" (or "Your") shall mean an individual or Legal Entity
-      exercising permissions granted by this License.
-
-      "Source" form shall mean the preferred form for making modifications,
-      including but not limited to software source code, documentation
-      source, and configuration files.
-
-      "Object" form shall mean any form resulting from mechanical
-      transformation or translation of a Source form, including but
-      not limited to compiled object code, generated documentation,
-      and conversions to other media types.
-
-      "Work" shall mean the work of authorship, whether in Source or
-      Object form, made available under the License, as indicated by a
-      copyright notice that is included in or attached to the work
-      (an example is provided in the Appendix below).
-
-      "Derivative Works" shall mean any work, whether in Source or Object
-      form, that is based on (or derived from) the Work and for which the
-      editorial revisions, annotations, elaborations, or other modifications
-      represent, as a whole, an original work of authorship. For the purposes
-      of this License, Derivative Works shall not include works that remain
-      separable from, or merely link (or bind by name) to the interfaces of,
-      the Work and Derivative Works thereof.
-
-      "Contribution" shall mean any work of authorship, including
-      the original version of the Work and any modifications or additions
-      to that Work or Derivative Works thereof, that is intentionally
-      submitted to Licensor for inclusion in the Work by the copyright owner
-      or by an individual or Legal Entity authorized to submit on behalf of
-      the copyright owner. For the purposes of this definition, "submitted"
-      means any form of electronic, verbal, or written communication sent
-      to the Licensor or its representatives, including but not limited to
-      communication on electronic mailing lists, source code control systems,
-      and issue tracking systems that are managed by, or on behalf of, the
-      Licensor for the purpose of discussing and improving the Work, but
-      excluding communication that is conspicuously marked or otherwise
-      designated in writing by the copyright owner as "Not a Contribution."
-
-      "Contributor" shall mean Licensor and any individual or Legal Entity
-      on behalf of whom a Contribution has been received by Licensor and
-      subsequently incorporated within the Work.
-
-   2. Grant of Copyright License. Subject to the terms and conditions of
-      this License, each Contributor hereby grants to You a perpetual,
-      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
-      copyright license to reproduce, prepare Derivative Works of,
-      publicly display, publicly perform, sublicense, and distribute the
-      Work and such Derivative Works in Source or Object form.
-
-   3. Grant of Patent License. Subject to the terms and conditions of
-      this License, each Contributor hereby grants to You a perpetual,
-      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
-      (except as stated in this section) patent license to make, have made,
-      use, offer to sell, sell, import, and otherwise transfer the Work,
-      where such license applies only to those patent claims licensable
-      by such Contributor that are necessarily infringed by their
-      Contribution(s) alone or by combination of their Contribution(s)
-      with the Work to which such Contribution(s) was submitted. If You
-      institute patent litigation against any entity (including a
-      cross-claim or counterclaim in a lawsuit) alleging that the Work
-      or a Contribution incorporated within the Work constitutes direct
-      or contributory patent infringement, then any patent licenses
-      granted to You under this License for that Work shall terminate
-      as of the date such litigation is filed.
-
-   4. Redistribution. You may reproduce and distribute copies of the
-      Work or Derivative Works thereof in any medium, with or without
-      modifications, and in Source or Object form, provided that You
-      meet the following conditions:
-
-      (a) You must give any other recipients of the Work or
-          Derivative Works a copy of this License; and
-
-      (b) You must cause any modified files to carry prominent notices
-          stating that You changed the files; and
-
-      (c) You must retain, in the Source form of any Derivative Works
-          that You distribute, all copyright, patent, trademark, and
-          attribution notices from the Source form of the Work,
-          excluding those notices that do not pertain to any part of
-          the Derivative Works; and
-
-      (d) If the Work includes a "NOTICE" text file as part of its
-          distribution, then any Derivative Works that You distribute must
-          include a readable copy of the attribution notices contained
-          within such NOTICE file, excluding those notices that do not
-          pertain to any part of the Derivative Works, in at least one
-          of the following places: within a NOTICE text file distributed
-          as part of the Derivative Works; within the Source form or
-          documentation, if provided along with the Derivative Works; or,
-          within a display generated by the Derivative Works, if and
-          wherever such third-party notices normally appear. The contents
-          of the NOTICE file are for informational purposes only and
-          do not modify the License. You may add Your own attribution
-          notices within Derivative Works that You distribute, alongside
-          or as an addendum to the NOTICE text from the Work, provided
-          that such additional attribution notices cannot be construed
-          as modifying the License.
-
-      You may add Your own copyright statement to Your modifications and
-      may provide additional or different license terms and conditions
-      for use, reproduction, or distribution of Your modifications, or
-      for any such Derivative Works as a whole, provided Your use,
-      reproduction, and distribution of the Work otherwise complies with
-      the conditions stated in this License.
-
-   5. Submission of Contributions. Unless You explicitly state otherwise,
-      any Contribution intentionally submitted for inclusion in the Work
-      by You to the Licensor shall be under the terms and conditions of
-      this License, without any additional terms or conditions.
-      Notwithstanding the above, nothing herein shall supersede or modify
-      the terms of any separate license agreement you may have executed
-      with Licensor regarding such Contributions.
-
-   6. Trademarks. This License does not grant permission to use the trade
-      names, trademarks, service marks, or product names of the Licensor,
-      except as required for reasonable and customary use in describing the
-      origin of the Work and reproducing the content of the NOTICE file.
-
-   7. Disclaimer of Warranty. Unless required by applicable law or
-      agreed to in writing, Licensor provides the Work (and each
-      Contributor provides its Contributions) on an "AS IS" BASIS,
-      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
-      implied, including, without limitation, any warranties or conditions
-      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
-      PARTICULAR PURPOSE. You are solely responsible for determining the
-      appropriateness of using or redistributing the Work and assume any
-      risks associated with Your exercise of permissions under this License.
-
-   8. Limitation of Liability. In no event and under no legal theory,
-      whether in tort (including negligence), contract, or otherwise,
-      unless required by applicable law (such as deliberate and grossly
-      negligent acts) or agreed to in writing, shall any Contributor be
-      liable to You for damages, including any direct, indirect, special,
-      incidental, or consequential damages of any character arising as a
-      result of this License or out of the use or inability to use the
-      Work (including but not limited to damages for loss of goodwill,
-      work stoppage, computer failure or malfunction, or any and all
-      other commercial damages or losses), even if such Contributor
-      has been advised of the possibility of such damages.
-
-   9. Accepting Warranty or Additional Liability. While redistributing
-      the Work or Derivative Works thereof, You may choose to offer,
-      and charge a fee for, acceptance of support, warranty, indemnity,
-      or other liability obligations and/or rights consistent with this
-      License. However, in accepting such obligations, You may act only
-      on Your own behalf and on Your sole responsibility, not on behalf
-      of any other Contributor, and only if You agree to indemnify,
-      defend, and hold each Contributor harmless for any liability
-      incurred by, or claims asserted against, such Contributor by reason
-      of your accepting any such warranty or additional liability.
-
-   END OF TERMS AND CONDITIONS
-
-   APPENDIX: How to apply the Apache License to your work.
-
-      To apply the Apache License to your work, attach the following
-      boilerplate notice, with the fields enclosed by brackets "[]"
-      replaced with your own identifying information. (Don't include
-      the brackets!)  The text should be enclosed in the appropriate
-      comment syntax for the file format. We also recommend that a
-      file or class name and description of purpose be included on the
-      same "printed page" as the copyright notice for easier
-      identification within third-party archives.
-
-   Copyright [yyyy] [name of copyright owner]
-
-   Licensed under the Apache License, Version 2.0 (the "License");
-   you may not use this file except in compliance with the License.
-   You may obtain a copy of the License at
-
-       http://www.apache.org/licenses/LICENSE-2.0
-
-   Unless required by applicable law or agreed to in writing, software
-   distributed under the License is distributed on an "AS IS" BASIS,
-   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-   See the License for the specific language governing permissions and
-   limitations under the License.
diff --git a/pkg/btree/README.md b/pkg/btree/README.md
deleted file mode 100644
index 6062a4dac..000000000
--- a/pkg/btree/README.md
+++ /dev/null
@@ -1,12 +0,0 @@
-# BTree implementation for Go
-
-![Travis CI Build Status](https://api.travis-ci.org/google/btree.svg?branch=master)
-
-This package provides an in-memory B-Tree implementation for Go, useful as
-an ordered, mutable data structure.
-
-The API is based off of the wonderful
-http://godoc.org/github.com/petar/GoLLRB/llrb, and is meant to allow btree to
-act as a drop-in replacement for gollrb trees.
-
-See http://godoc.org/github.com/google/btree for documentation.
diff --git a/pkg/btree/btree.go b/pkg/btree/btree_generic.go
similarity index 73%
rename from pkg/btree/btree.go
rename to pkg/btree/btree_generic.go
index 2d1f85f76..634a24b5b 100644
--- a/pkg/btree/btree.go
+++ b/pkg/btree/btree_generic.go
@@ -1,4 +1,4 @@
-// Copyright 2014 Google Inc.
+// Copyright 2014-2022 Google Inc.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
@@ -12,10 +12,10 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-// This package is a modified version of google/btree. Change as follows:
-//   * Add `indices` array for `node`, and related codes to maintain it.
-//     This modification may affect performance of insertion and deletion.
-//   * Add `GetAt` and `GetWithIndex` method for `BTree`.
+// In Go 1.18 and beyond, a BTreeG generic is created, and BTree is a specific
+// instantiation of that generic for the Item interface, with a backwards-
+// compatible API.  Before go1.18, generics are not supported,
+// and BTree is just an implementation based around the Item interface.
 
 // Package btree implements in-memory B-Trees of arbitrary degree.
 //
@@ -53,22 +53,42 @@
 // Its functions, therefore, exactly mirror those of
 // llrb.LLRB where possible.  Unlike gollrb, though, we currently don't
 // support storing multiple equivalent values.
+//
+// There are two implementations; those suffixed with 'G' are generics, usable
+// for any type, and require a passed-in "less" function to define their ordering.
+// Those without this prefix are specific to the 'Item' interface, and use
+// its 'Less' function for ordering.
+
+// Copyright 2022 TiKV Project Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//	http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//revive:disable
 package btree
 
 import (
 	"sort"
-
-	"github.com/tikv/pd/pkg/syncutil"
+	"sync"
 )
 
 // Item represents a single object in the tree.
-type Item interface {
+type Item[T any] interface {
 	// Less tests whether the current item is less than the given argument.
 	//
 	// This must provide a strict weak ordering.
 	// If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only
 	// hold one of either a or b in the tree).
-	Less(than Item) bool
+	Less(than T) bool
 }
 
 const (
@@ -76,32 +96,27 @@ const (
 	DefaultFreeListSize = 32
 )
 
-var (
-	nilItems    = make(items, 16)
-	nilChildren = make(children, 16)
-)
-
-// FreeList represents a free list of btree nodes. By default each
+// FreeListG represents a free list of btree nodes. By default each
 // BTree has its own FreeList, but multiple BTrees can share the same
-// FreeList.
+// FreeList, in particular when they're created with Clone.
 // Two Btrees using the same freelist are safe for concurrent write access.
-type FreeList struct {
-	mu       syncutil.Mutex
-	freelist []*node
+type FreeListG[T Item[T]] struct {
+	mu       sync.Mutex
+	freelist []*node[T]
 }
 
-// NewFreeList creates a new free list.
+// NewFreeListG creates a new free list.
 // size is the maximum size of the returned free list.
-func NewFreeList(size int) *FreeList {
-	return &FreeList{freelist: make([]*node, 0, size)}
+func NewFreeListG[T Item[T]](size int) *FreeListG[T] {
+	return &FreeListG[T]{freelist: make([]*node[T], 0, size)}
 }
 
-func (f *FreeList) newNode() (n *node) {
+func (f *FreeListG[T]) newNode() (n *node[T]) {
 	f.mu.Lock()
 	index := len(f.freelist) - 1
 	if index < 0 {
 		f.mu.Unlock()
-		return new(node)
+		return new(node[T])
 	}
 	n = f.freelist[index]
 	f.freelist[index] = nil
@@ -110,9 +125,7 @@ func (f *FreeList) newNode() (n *node) {
 	return
 }
 
-// freeNode adds the given node to the list, returning true if it was added
-// and false if it was discarded.
-func (f *FreeList) freeNode(n *node) (out bool) {
+func (f *FreeListG[T]) freeNode(n *node[T]) (out bool) {
 	f.mu.Lock()
 	if len(f.freelist) < cap(f.freelist) {
 		f.freelist = append(f.freelist, n)
@@ -122,37 +135,40 @@ func (f *FreeList) freeNode(n *node) (out bool) {
 	return
 }
 
-// ItemIterator allows callers of Ascend* to iterate in-order over portions of
+// ItemIteratorG allows callers of Ascend* to iterate in-order over portions of
 // the tree.  When this function returns false, iteration will stop and the
 // associated Ascend* function will immediately return.
-type ItemIterator func(i Item) bool
+type ItemIteratorG[T Item[T]] func(i T) bool
 
-// New creates a new B-Tree with the given degree.
+// NewG creates a new B-Tree with the given degree.
 //
-// New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items
+// NewG(2), for example, will create a 2-3-4 tree (each node contains 1-3 items
 // and 2-4 children).
-func New(degree int) *BTree {
-	return NewWithFreeList(degree, NewFreeList(DefaultFreeListSize))
+//
+// The passed-in LessFunc determines how objects of type T are ordered.
+func NewG[T Item[T]](degree int) *BTreeG[T] {
+	return NewWithFreeListG(degree, NewFreeListG[T](DefaultFreeListSize))
 }
 
-// NewWithFreeList creates a new B-Tree that uses the given node free list.
-func NewWithFreeList(degree int, f *FreeList) *BTree {
+// NewWithFreeListG creates a new B-Tree that uses the given node free list.
+func NewWithFreeListG[T Item[T]](degree int, f *FreeListG[T]) *BTreeG[T] {
 	if degree <= 1 {
 		panic("bad degree")
 	}
-	return &BTree{
+	return &BTreeG[T]{
 		degree: degree,
-		cow:    &copyOnWriteContext{freelist: f},
+		cow:    &copyOnWriteContext[T]{freelist: f},
 	}
 }
 
 // items stores items in a node.
-type items []Item
+type items[T Item[T]] []T
 
 // insertAt inserts a value into the given index, pushing all subsequent values
 // forward.
-func (s *items) insertAt(index int, item Item) {
-	*s = append(*s, nil)
+func (s *items[T]) insertAt(index int, item T) {
+	var zero T
+	*s = append(*s, zero)
 	if index < len(*s) {
 		copy((*s)[index+1:], (*s)[index:])
 	}
@@ -161,37 +177,44 @@ func (s *items) insertAt(index int, item Item) {
 
 // removeAt removes a value at a given index, pulling all subsequent values
 // back.
-func (s *items) removeAt(index int) Item {
+func (s *items[T]) removeAt(index int) T {
 	item := (*s)[index]
 	copy((*s)[index:], (*s)[index+1:])
-	(*s)[len(*s)-1] = nil
+	var zero T
+	(*s)[len(*s)-1] = zero
 	*s = (*s)[:len(*s)-1]
 	return item
 }
 
 // pop removes and returns the last element in the list.
-func (s *items) pop() (out Item) {
+func (s *items[T]) pop() (out T) {
 	index := len(*s) - 1
 	out = (*s)[index]
-	(*s)[index] = nil
+	var zero T
+	(*s)[index] = zero
 	*s = (*s)[:index]
 	return
 }
 
 // truncate truncates this instance at index so that it contains only the
 // first index items. index must be less than or equal to length.
-func (s *items) truncate(index int) {
-	var toClear items
+func (s *items[T]) truncate(index int) {
+	var i int
+	var x T
+	var toClear items[T]
 	*s, toClear = (*s)[:index], (*s)[index:]
 	for len(toClear) > 0 {
-		toClear = toClear[copy(toClear, nilItems):]
+		for i = 0; i < 16 && i < len(toClear); i++ {
+			toClear[i] = x
+		}
+		toClear = toClear[i:]
 	}
 }
 
 // find returns the index where the given item should be inserted into this
 // list.  'found' is true if the item already exists in the list at the given
 // index.
-func (s items) find(item Item) (index int, found bool) {
+func (s items[T]) find(item T) (index int, found bool) {
 	i := sort.Search(len(s), func(i int) bool {
 		return item.Less(s[i])
 	})
@@ -201,48 +224,6 @@ func (s items) find(item Item) (index int, found bool) {
 	return i, false
 }
 
-// children stores child nodes in a node.
-type children []*node
-
-// insertAt inserts a value into the given index, pushing all subsequent values
-// forward.
-func (s *children) insertAt(index int, n *node) {
-	*s = append(*s, nil)
-	if index < len(*s) {
-		copy((*s)[index+1:], (*s)[index:])
-	}
-	(*s)[index] = n
-}
-
-// removeAt removes a value at a given index, pulling all subsequent values
-// back.
-func (s *children) removeAt(index int) *node {
-	n := (*s)[index]
-	copy((*s)[index:], (*s)[index+1:])
-	(*s)[len(*s)-1] = nil
-	*s = (*s)[:len(*s)-1]
-	return n
-}
-
-// pop removes and returns the last element in the list.
-func (s *children) pop() (out *node) {
-	index := len(*s) - 1
-	out = (*s)[index]
-	(*s)[index] = nil
-	*s = (*s)[:index]
-	return
-}
-
-// truncate truncates this instance at index so that it contains only the
-// first index children. index must be less than or equal to length.
-func (s *children) truncate(index int) {
-	var toClear children
-	*s, toClear = (*s)[:index], (*s)[index:]
-	for len(toClear) > 0 {
-		toClear = toClear[copy(toClear, nilChildren):]
-	}
-}
-
 // indices stores indices of items in a node.
 // If the node has any children, indices[i] is the index of items[i] in the subtree.
 // We have following formulas:
@@ -275,7 +256,7 @@ func (s *indices) push(sz int) {
 	}
 }
 
-// children[i] is splited.
+// children[i] is split.
 func (s *indices) split(index, nextSize int) {
 	s.insertAt(index+1, -1)
 	(*s)[index] -= 1 + nextSize
@@ -321,26 +302,72 @@ func (s indices) find(k int) (index int, found bool) {
 	return i, s[i] == k
 }
 
+// children stores child nodes in a node.
+type children[T Item[T]] []*node[T]
+
+// insertAt inserts a value into the given index, pushing all subsequent values
+// forward.
+func (s *children[T]) insertAt(index int, n *node[T]) {
+	*s = append(*s, nil)
+	if index < len(*s) {
+		copy((*s)[index+1:], (*s)[index:])
+	}
+	(*s)[index] = n
+}
+
+// removeAt removes a value at a given index, pulling all subsequent values
+// back.
+func (s *children[T]) removeAt(index int) *node[T] {
+	n := (*s)[index]
+	copy((*s)[index:], (*s)[index+1:])
+	(*s)[len(*s)-1] = nil
+	*s = (*s)[:len(*s)-1]
+	return n
+}
+
+// pop removes and returns the last element in the list.
+func (s *children[T]) pop() (out *node[T]) {
+	index := len(*s) - 1
+	out = (*s)[index]
+	(*s)[index] = nil
+	*s = (*s)[:index]
+	return
+}
+
+// truncate truncates this instance at index so that it contains only the
+// first index children. index must be less than or equal to length.
+func (s *children[T]) truncate(index int) {
+	var i int
+	var toClear children[T]
+	*s, toClear = (*s)[:index], (*s)[index:]
+	for len(toClear) > 0 {
+		for i = 0; i < 16 && i < len(toClear); i++ {
+			toClear[i] = nil
+		}
+		toClear = toClear[i:]
+	}
+}
+
 // node is an internal node in a tree.
 //
 // It must at all times maintain the invariant that either
 //   - len(children) == 0, len(items) unconstrained
 //   - len(children) == len(items) + 1
-type node struct {
-	items    items
-	children children
+type node[T Item[T]] struct {
+	items    items[T]
+	children children[T]
 	indices  indices
-	cow      *copyOnWriteContext
+	cow      *copyOnWriteContext[T]
 }
 
-func (n *node) length() int {
+func (n *node[T]) length() int {
 	if len(n.indices) == 0 {
 		return len(n.items)
 	}
 	return n.indices[len(n.indices)-1]
 }
 
-func (n *node) initSize() {
+func (n *node[T]) initSize() {
 	l := len(n.children)
 	if l <= 0 {
 		n.indices.truncate(0)
@@ -356,7 +383,7 @@ func (n *node) initSize() {
 	}
 }
 
-func (n *node) mutableFor(cow *copyOnWriteContext) *node {
+func (n *node[T]) mutableFor(cow *copyOnWriteContext[T]) *node[T] {
 	if n.cow == cow {
 		return n
 	}
@@ -364,14 +391,14 @@ func (n *node) mutableFor(cow *copyOnWriteContext) *node {
 	if cap(out.items) >= len(n.items) {
 		out.items = out.items[:len(n.items)]
 	} else {
-		out.items = make(items, len(n.items), cap(n.items))
+		out.items = make(items[T], len(n.items), cap(n.items))
 	}
 	copy(out.items, n.items)
 	// Copy children
 	if cap(out.children) >= len(n.children) {
 		out.children = out.children[:len(n.children)]
 	} else {
-		out.children = make(children, len(n.children), cap(n.children))
+		out.children = make(children[T], len(n.children), cap(n.children))
 	}
 	copy(out.children, n.children)
 	// Copy indices
@@ -384,7 +411,7 @@ func (n *node) mutableFor(cow *copyOnWriteContext) *node {
 	return out
 }
 
-func (n *node) mutableChild(i int) *node {
+func (n *node[T]) mutableChild(i int) *node[T] {
 	c := n.children[i].mutableFor(n.cow)
 	n.children[i] = c
 	return c
@@ -393,7 +420,7 @@ func (n *node) mutableChild(i int) *node {
 // split splits the given node at the given index.  The current node shrinks,
 // and this function returns the item that existed at that index and a new node
 // containing all items/children after it.
-func (n *node) split(i int) (Item, *node) {
+func (n *node[T]) split(i int) (T, *node[T]) {
 	item := n.items[i]
 	next := n.cow.newNode()
 	next.items = append(next.items, n.items[i+1:]...)
@@ -409,7 +436,7 @@ func (n *node) split(i int) (Item, *node) {
 
 // maybeSplitChild checks if a child should be split, and if so splits it.
 // Returns whether or not a split occurred.
-func (n *node) maybeSplitChild(i, maxItems int) bool {
+func (n *node[T]) maybeSplitChild(i, maxItems int) bool {
 	if len(n.children[i].items) < maxItems {
 		return false
 	}
@@ -424,16 +451,16 @@ func (n *node) maybeSplitChild(i, maxItems int) bool {
 // insert inserts an item into the subtree rooted at this node, making sure
 // no nodes in the subtree exceed maxItems items.  Should an equivalent item be
 // be found/replaced by insert, it will be returned.
-func (n *node) insert(item Item, maxItems int) Item {
+func (n *node[T]) insert(item T, maxItems int) (_ T, _ bool) {
 	i, found := n.items.find(item)
 	if found {
 		out := n.items[i]
 		n.items[i] = item
-		return out
+		return out, true
 	}
 	if len(n.children) == 0 {
 		n.items.insertAt(i, item)
-		return nil
+		return
 	}
 	if n.maybeSplitChild(i, maxItems) {
 		inTree := n.items[i]
@@ -445,19 +472,31 @@ func (n *node) insert(item Item, maxItems int) Item {
 		default:
 			out := n.items[i]
 			n.items[i] = item
-			return out
+			return out, true
 		}
 	}
-	out := n.mutableChild(i).insert(item, maxItems)
-	if out == nil {
+	out, outb := n.mutableChild(i).insert(item, maxItems)
+	if !outb {
 		n.indices.addAt(i, 1)
 	}
-	return out
+	return out, outb
+}
+
+// get finds the given key in the subtree and returns it.
+func (n *node[T]) get(key T) (_ T, _ bool) {
+	i, found := n.items.find(key)
+	if found {
+		return n.items[i], true
+	} else if len(n.children) > 0 {
+		return n.children[i].get(key)
+	}
+	return
 }
 
-func (n *node) getAt(k int) Item {
+func (n *node[T]) getAt(k int) T {
 	if k >= n.length() || k < 0 {
-		return nil
+		var zero T
+		return zero
 	}
 	if len(n.children) == 0 {
 		return n.items[k]
@@ -473,7 +512,7 @@ func (n *node) getAt(k int) Item {
 }
 
 // index is the number of items < key
-func (n *node) getWithIndex(key Item) (Item, int) {
+func (n *node[T]) getWithIndex(key T) (_ T, _ int) {
 	i, found := n.items.find(key)
 	if found {
 		rk := i
@@ -488,46 +527,36 @@ func (n *node) getWithIndex(key Item) (Item, int) {
 		}
 		return out, rk
 	}
-	return nil, i
-}
-
-// get finds the given key in the subtree and returns it.
-func (n *node) get(key Item) Item {
-	i, found := n.items.find(key)
-	if found {
-		return n.items[i]
-	} else if len(n.children) > 0 {
-		return n.children[i].get(key)
-	}
-	return nil
+	var zero T
+	return zero, i
 }
 
 // min returns the first item in the subtree.
-func min(n *node) Item {
+func min[T Item[T]](n *node[T]) (_ T, found bool) {
 	if n == nil {
-		return nil
+		return
 	}
 	for len(n.children) > 0 {
 		n = n.children[0]
 	}
 	if len(n.items) == 0 {
-		return nil
+		return
 	}
-	return n.items[0]
+	return n.items[0], true
 }
 
 // max returns the last item in the subtree.
-func max(n *node) Item {
+func max[T Item[T]](n *node[T]) (_ T, found bool) {
 	if n == nil {
-		return nil
+		return
 	}
 	for len(n.children) > 0 {
 		n = n.children[len(n.children)-1]
 	}
 	if len(n.items) == 0 {
-		return nil
+		return
 	}
-	return n.items[len(n.items)-1]
+	return n.items[len(n.items)-1], true
 }
 
 // toRemove details what item to remove in a node.remove call.
@@ -540,27 +569,27 @@ const (
 )
 
 // remove removes an item from the subtree rooted at this node.
-func (n *node) remove(item Item, minItems int, typ toRemove) (out Item) {
+func (n *node[T]) remove(item T, minItems int, typ toRemove) (_ T, _ bool) {
 	var i int
 	var found bool
 	switch typ {
 	case removeMax:
 		if len(n.children) == 0 {
-			return n.items.pop()
+			return n.items.pop(), true
 		}
 		i = len(n.items)
 	case removeMin:
 		if len(n.children) == 0 {
-			return n.items.removeAt(0)
+			return n.items.removeAt(0), true
 		}
 		i = 0
 	case removeItem:
 		i, found = n.items.find(item)
 		if len(n.children) == 0 {
 			if found {
-				return n.items.removeAt(i)
+				return n.items.removeAt(i), true
 			}
-			return nil
+			return
 		}
 	default:
 		panic("invalid type")
@@ -573,6 +602,10 @@ func (n *node) remove(item Item, minItems int, typ toRemove) (out Item) {
 	// Either we had enough items to begin with, or we've done some
 	// merging/stealing, because we've got enough now and we're ready to return
 	// stuff.
+	var (
+		out  T
+		outb bool
+	)
 	if found {
 		// The item exists at index 'i', and the child we've selected can give us a
 		// predecessor, since if we've gotten here it's got > minItems items in it.
@@ -580,16 +613,17 @@ func (n *node) remove(item Item, minItems int, typ toRemove) (out Item) {
 		// We use our special-case 'remove' call with typ=maxItem to pull the
 		// predecessor of item i (the rightmost leaf of our immediate left child)
 		// and set it into where we pulled the item from.
-		n.items[i] = child.remove(nil, minItems, removeMax)
+		var zero T
+		n.items[i], outb = child.remove(zero, minItems, removeMax)
 	} else {
 		// Final recursive call.  Once we're here, we know that the item isn't in this
 		// node and that the child is big enough to remove from.
-		out = child.remove(item, minItems, typ)
+		out, outb = child.remove(item, minItems, typ)
 	}
-	if out != nil {
+	if outb {
 		n.indices.addAt(i, -1)
 	}
-	return
+	return out, outb
 }
 
 // growChildAndRemove grows child 'i' to make sure it's possible to remove an
@@ -616,7 +650,7 @@ func (n *node) remove(item Item, minItems int, typ toRemove) (out Item) {
 // We then simply redo our remove call, and the second time (regardless of
 // whether we're in case 1 or 2), we'll have enough items and can guarantee
 // that we hit case A.
-func (n *node) growChildAndRemove(i int, item Item, minItems int, typ toRemove) Item {
+func (n *node[T]) growChildAndRemove(i int, item T, minItems int, typ toRemove) (T, bool) {
 	if i > 0 && len(n.children[i-1].items) > minItems {
 		// Steal from left child
 		child := n.mutableChild(i)
@@ -679,13 +713,13 @@ const (
 // will force the iterator to include the first item when it equals 'start',
 // thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a
 // "greaterThan" or "lessThan" queries.
-func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit bool, iter ItemIterator) (bool, bool) { // revive:disable-line:confusing-results
+func (n *node[T]) iterate(dir direction, start, stop *T, includeStart bool, hit bool, iter ItemIteratorG[T]) (bool, bool) {
 	var ok, found bool
 	var index int
 	switch dir {
 	case ascend:
 		if start != nil {
-			index, _ = n.items.find(start)
+			index, _ = n.items.find(*start)
 		}
 		for i := index; i < len(n.items); i++ {
 			if len(n.children) > 0 {
@@ -693,12 +727,12 @@ func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit b
 					return hit, false
 				}
 			}
-			if !includeStart && !hit && start != nil && !start.Less(n.items[i]) {
+			if !includeStart && !hit && start != nil && !(*start).Less(n.items[i]) {
 				hit = true
 				continue
 			}
 			hit = true
-			if stop != nil && !n.items[i].Less(stop) {
+			if stop != nil && !n.items[i].Less(*stop) {
 				return hit, false
 			}
 			if !iter(n.items[i]) {
@@ -712,7 +746,7 @@ func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit b
 		}
 	case descend:
 		if start != nil {
-			index, found = n.items.find(start)
+			index, found = n.items.find(*start)
 			if !found {
 				index--
 			}
@@ -720,8 +754,8 @@ func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit b
 			index = len(n.items) - 1
 		}
 		for i := index; i >= 0; i-- {
-			if start != nil && !n.items[i].Less(start) {
-				if !includeStart || hit || start.Less(n.items[i]) {
+			if start != nil && !n.items[i].Less(*start) {
+				if !includeStart || hit || (*start).Less(n.items[i]) {
 					continue
 				}
 			}
@@ -730,7 +764,7 @@ func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit b
 					return hit, false
 				}
 			}
-			if stop != nil && !stop.Less(n.items[i]) {
+			if stop != nil && !(*stop).Less(n.items[i]) {
 				return hit, false //	continue
 			}
 			hit = true
@@ -747,18 +781,18 @@ func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit b
 	return hit, true
 }
 
-// BTree is an implementation of a B-Tree.
+// BTreeG is a generic implementation of a B-Tree.
 //
-// BTree stores Item instances in an ordered structure, allowing easy insertion,
+// BTreeG stores items of type T in an ordered structure, allowing easy insertion,
 // removal, and iteration.
 //
 // Write operations are not safe for concurrent mutation by multiple
 // goroutines, but Read operations are.
-type BTree struct {
+type BTreeG[T Item[T]] struct {
 	degree int
 	length int
-	root   *node
-	cow    *copyOnWriteContext
+	root   *node[T]
+	cow    *copyOnWriteContext[T]
 }
 
 // copyOnWriteContext pointers determine node ownership... a tree with a write
@@ -775,8 +809,8 @@ type BTree struct {
 // tree's context, that node is modifiable in place.  Children of that node may
 // not share context, but before we descend into them, we'll make a mutable
 // copy.
-type copyOnWriteContext struct {
-	freelist *FreeList
+type copyOnWriteContext[T Item[T]] struct {
+	freelist *FreeListG[T]
 }
 
 // Clone clones the btree, lazily.  Clone should not be called concurrently,
@@ -790,7 +824,7 @@ type copyOnWriteContext struct {
 // will initially experience minor slow-downs caused by additional allocs and
 // copies due to the aforementioned copy-on-write logic, but should converge to
 // the original performance characteristics of the original tree.
-func (t *BTree) Clone() (t2 *BTree) {
+func (t *BTreeG[T]) Clone() (t2 *BTreeG[T]) {
 	// Create two entirely new copy-on-write contexts.
 	// This operation effectively creates three trees:
 	//   the original, shared nodes (old b.cow)
@@ -804,17 +838,17 @@ func (t *BTree) Clone() (t2 *BTree) {
 }
 
 // maxItems returns the max number of items to allow per node.
-func (t *BTree) maxItems() int {
+func (t *BTreeG[T]) maxItems() int {
 	return t.degree*2 - 1
 }
 
 // minItems returns the min number of items to allow per node (ignored for the
 // root node).
-func (t *BTree) minItems() int {
+func (t *BTreeG[T]) minItems() int {
 	return t.degree - 1
 }
 
-func (c *copyOnWriteContext) newNode() (n *node) {
+func (c *copyOnWriteContext[T]) newNode() (n *node[T]) {
 	n = c.freelist.newNode()
 	n.cow = c
 	return
@@ -831,7 +865,7 @@ const (
 // freeNode frees a node within a given COW context, if it's owned by that
 // context.  It returns what happened to the node (see freeType const
 // documentation).
-func (c *copyOnWriteContext) freeNode(n *node) freeType {
+func (c *copyOnWriteContext[T]) freeNode(n *node[T]) freeType {
 	if n.cow == c {
 		// clear to allow GC
 		n.items.truncate(0)
@@ -847,19 +881,16 @@ func (c *copyOnWriteContext) freeNode(n *node) freeType {
 }
 
 // ReplaceOrInsert adds the given item to the tree.  If an item in the tree
-// already equals the given one, it is removed from the tree and returned.
-// Otherwise, nil is returned.
+// already equals the given one, it is removed from the tree and returned,
+// and the second return value is true.  Otherwise, (zeroValue, false)
 //
 // nil cannot be added to the tree (will panic).
-func (t *BTree) ReplaceOrInsert(item Item) Item {
-	if item == nil {
-		panic("nil item being added to BTree")
-	}
+func (t *BTreeG[T]) ReplaceOrInsert(item T) (_ T, _ bool) {
 	if t.root == nil {
 		t.root = t.cow.newNode()
 		t.root.items = append(t.root.items, item)
 		t.length++
-		return nil
+		return
 	}
 	t.root = t.root.mutableFor(t.cow)
 	if len(t.root.items) >= t.maxItems() {
@@ -870,78 +901,80 @@ func (t *BTree) ReplaceOrInsert(item Item) Item {
 		t.root.children = append(t.root.children, oldroot, second)
 		t.root.initSize()
 	}
-	out := t.root.insert(item, t.maxItems())
-	if out == nil {
+	out, found := t.root.insert(item, t.maxItems())
+	if !found {
 		t.length++
 	}
-	return out
+	return out, found
 }
 
 // Delete removes an item equal to the passed in item from the tree, returning
-// it.  If no such item exists, returns nil.
-func (t *BTree) Delete(item Item) Item {
+// it.  If no such item exists, returns (zeroValue, false).
+func (t *BTreeG[T]) Delete(item T) (T, bool) {
 	return t.deleteItem(item, removeItem)
 }
 
 // DeleteMin removes the smallest item in the tree and returns it.
-// If no such item exists, returns nil.
-func (t *BTree) DeleteMin() Item {
-	return t.deleteItem(nil, removeMin)
+// If no such item exists, returns (zeroValue, false).
+func (t *BTreeG[T]) DeleteMin() (T, bool) {
+	var zero T
+	return t.deleteItem(zero, removeMin)
 }
 
 // DeleteMax removes the largest item in the tree and returns it.
-// If no such item exists, returns nil.
-func (t *BTree) DeleteMax() Item {
-	return t.deleteItem(nil, removeMax)
+// If no such item exists, returns (zeroValue, false).
+func (t *BTreeG[T]) DeleteMax() (T, bool) {
+	var zero T
+	return t.deleteItem(zero, removeMax)
 }
 
-func (t *BTree) deleteItem(item Item, typ toRemove) Item {
+func (t *BTreeG[T]) deleteItem(item T, typ toRemove) (_ T, _ bool) {
 	if t.root == nil || len(t.root.items) == 0 {
-		return nil
+		return
 	}
 	t.root = t.root.mutableFor(t.cow)
-	out := t.root.remove(item, t.minItems(), typ)
+	out, found := t.root.remove(item, t.minItems(), typ)
 	if len(t.root.items) == 0 && len(t.root.children) > 0 {
 		oldroot := t.root
 		t.root = t.root.children[0]
 		t.cow.freeNode(oldroot)
 	}
-	if out != nil {
+	if found {
 		t.length--
 	}
-	return out
+	return out, found
 }
 
 // AscendRange calls the iterator for every value in the tree within the range
 // [greaterOrEqual, lessThan), until iterator returns false.
-func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator) {
+func (t *BTreeG[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIteratorG[T]) {
 	if t.root == nil {
 		return
 	}
-	t.root.iterate(ascend, greaterOrEqual, lessThan, true, false, iterator)
+	t.root.iterate(ascend, &greaterOrEqual, &lessThan, true, false, iterator)
 }
 
 // AscendLessThan calls the iterator for every value in the tree within the range
 // [first, pivot), until iterator returns false.
-func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator) {
+func (t *BTreeG[T]) AscendLessThan(pivot T, iterator ItemIteratorG[T]) {
 	if t.root == nil {
 		return
 	}
-	t.root.iterate(ascend, nil, pivot, false, false, iterator)
+	t.root.iterate(ascend, nil, &pivot, false, false, iterator)
 }
 
 // AscendGreaterOrEqual calls the iterator for every value in the tree within
 // the range [pivot, last], until iterator returns false.
-func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) {
+func (t *BTreeG[T]) AscendGreaterOrEqual(pivot T, iterator ItemIteratorG[T]) {
 	if t.root == nil {
 		return
 	}
-	t.root.iterate(ascend, pivot, nil, true, false, iterator)
+	t.root.iterate(ascend, &pivot, nil, true, false, iterator)
 }
 
 // Ascend calls the iterator for every value in the tree within the range
 // [first, last], until iterator returns false.
-func (t *BTree) Ascend(iterator ItemIterator) {
+func (t *BTreeG[T]) Ascend(iterator ItemIteratorG[T]) {
 	if t.root == nil {
 		return
 	}
@@ -950,88 +983,91 @@ func (t *BTree) Ascend(iterator ItemIterator) {
 
 // DescendRange calls the iterator for every value in the tree within the range
 // [lessOrEqual, greaterThan), until iterator returns false.
-func (t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator) {
+func (t *BTreeG[T]) DescendRange(lessOrEqual, greaterThan T, iterator ItemIteratorG[T]) {
 	if t.root == nil {
 		return
 	}
-	t.root.iterate(descend, lessOrEqual, greaterThan, true, false, iterator)
+	t.root.iterate(descend, &lessOrEqual, &greaterThan, true, false, iterator)
 }
 
 // DescendLessOrEqual calls the iterator for every value in the tree within the range
 // [pivot, first], until iterator returns false.
-func (t *BTree) DescendLessOrEqual(pivot Item, iterator ItemIterator) {
+func (t *BTreeG[T]) DescendLessOrEqual(pivot T, iterator ItemIteratorG[T]) {
 	if t.root == nil {
 		return
 	}
-	t.root.iterate(descend, pivot, nil, true, false, iterator)
+	t.root.iterate(descend, &pivot, nil, true, false, iterator)
 }
 
 // DescendGreaterThan calls the iterator for every value in the tree within
-// the range (pivot, last], until iterator returns false.
-func (t *BTree) DescendGreaterThan(pivot Item, iterator ItemIterator) {
+// the range [last, pivot), until iterator returns false.
+func (t *BTreeG[T]) DescendGreaterThan(pivot T, iterator ItemIteratorG[T]) {
 	if t.root == nil {
 		return
 	}
-	t.root.iterate(descend, nil, pivot, false, false, iterator)
+	t.root.iterate(descend, nil, &pivot, false, false, iterator)
 }
 
 // Descend calls the iterator for every value in the tree within the range
 // [last, first], until iterator returns false.
-func (t *BTree) Descend(iterator ItemIterator) {
+func (t *BTreeG[T]) Descend(iterator ItemIteratorG[T]) {
 	if t.root == nil {
 		return
 	}
 	t.root.iterate(descend, nil, nil, false, false, iterator)
 }
 
-// Get looks for the key item in the tree, returning it.  It returns nil if
-// unable to find that item.
-func (t *BTree) Get(key Item) Item {
+// Get looks for the key item in the tree, returning it.  It returns
+// (zeroValue, false) if unable to find that item.
+func (t *BTreeG[T]) Get(key T) (_ T, _ bool) {
 	if t.root == nil {
-		return nil
+		return
 	}
 	return t.root.get(key)
 }
 
 // GetWithIndex gets the key and its index.
 // If the key is not in the tree, the the index is the number of items < key.
-func (t *BTree) GetWithIndex(key Item) (Item, int) {
+func (t *BTreeG[T]) GetWithIndex(key T) (_ T, _ int) {
 	if t.root == nil {
-		return nil, 0
+		var zero T
+		return zero, 0
 	}
 	return t.root.getWithIndex(key)
 }
 
 // GetAt returns the item with index k. If k < 0 or k >= t.Len(), returns nil.
-func (t *BTree) GetAt(k int) Item {
+func (t *BTreeG[T]) GetAt(k int) T {
 	if t.root == nil {
-		return nil
+		var zero T
+		return zero
 	}
 	return t.root.getAt(k)
 }
 
-// Min returns the smallest item in the tree, or nil if the tree is empty.
-func (t *BTree) Min() Item {
+// Min returns the smallest item in the tree, or (zeroValue, false) if the tree is empty.
+func (t *BTreeG[T]) Min() (_ T, _ bool) {
 	return min(t.root)
 }
 
-// Max returns the largest item in the tree, or nil if the tree is empty.
-func (t *BTree) Max() Item {
+// Max returns the largest item in the tree, or (zeroValue, false) if the tree is empty.
+func (t *BTreeG[T]) Max() (_ T, _ bool) {
 	return max(t.root)
 }
 
 // Has returns true if the given key is in the tree.
-func (t *BTree) Has(key Item) bool {
-	return t.Get(key) != nil
+func (t *BTreeG[T]) Has(key T) bool {
+	_, found := t.Get(key)
+	return found
 }
 
 // Len returns the number of items currently in the tree.
-func (t *BTree) Len() int {
+func (t *BTreeG[T]) Len() int {
 	return t.length
 }
 
 // function for test.
-func (t *BTree) getRootLength() int {
+func (t *BTreeG[T]) getRootLength() int {
 	if t.root == nil {
 		return 0
 	}
@@ -1059,7 +1095,7 @@ func (t *BTree) getRootLength() int {
 //	O(tree size):  when all nodes are owned by another tree, all nodes are
 //	    iterated over looking for nodes to add to the freelist, and due to
 //	    ownership, none are.
-func (t *BTree) Clear(addNodesToFreelist bool) {
+func (t *BTreeG[T]) Clear(addNodesToFreelist bool) {
 	if t.root != nil && addNodesToFreelist {
 		t.root.reset(t.cow)
 	}
@@ -1069,7 +1105,7 @@ func (t *BTree) Clear(addNodesToFreelist bool) {
 // reset returns a subtree to the freelist.  It breaks out immediately if the
 // freelist is full, since the only benefit of iterating is to fill that
 // freelist up.  Returns true if parent reset call should continue.
-func (n *node) reset(c *copyOnWriteContext) bool {
+func (n *node[T]) reset(c *copyOnWriteContext[T]) bool {
 	for _, child := range n.children {
 		if !child.reset(c) {
 			return false
@@ -1082,6 +1118,6 @@ func (n *node) reset(c *copyOnWriteContext) bool {
 type Int int
 
 // Less returns true if int(a) < int(b).
-func (a Int) Less(b Item) bool {
-	return a < b.(Int)
+func (a Int) Less(b Int) bool {
+	return a < b
 }
diff --git a/pkg/btree/btree_mem.go b/pkg/btree/btree_mem.go
deleted file mode 100644
index 21ee62bce..000000000
--- a/pkg/btree/btree_mem.go
+++ /dev/null
@@ -1,77 +0,0 @@
-// Copyright 2014 Google Inc.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//     http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-//go:build ignore
-// +build ignore
-
-// This binary compares memory usage between btree and gollrb.
-package main
-
-import (
-	"flag"
-	"fmt"
-	"math/rand"
-	"runtime"
-	"time"
-
-	"github.com/google/btree"
-	"github.com/petar/GoLLRB/llrb"
-)
-
-var (
-	size   = flag.Int("size", 1000000, "size of the tree to build")
-	degree = flag.Int("degree", 8, "degree of btree")
-	gollrb = flag.Bool("llrb", false, "use llrb instead of btree")
-)
-
-func main() {
-	flag.Parse()
-	vals := rand.Perm(*size)
-	var t, v interface{}
-	v = vals
-	var stats runtime.MemStats
-	for i := 0; i < 10; i++ {
-		runtime.GC()
-	}
-	fmt.Println("-------- BEFORE ----------")
-	runtime.ReadMemStats(&stats)
-	fmt.Printf("%+v\n", stats)
-	start := time.Now()
-	if *gollrb {
-		tr := llrb.New()
-		for _, v := range vals {
-			tr.ReplaceOrInsert(llrb.Int(v))
-		}
-		t = tr // keep it around
-	} else {
-		tr := btree.New(*degree)
-		for _, v := range vals {
-			tr.ReplaceOrInsert(btree.Int(v))
-		}
-		t = tr // keep it around
-	}
-	fmt.Printf("%v inserts in %v\n", *size, time.Since(start))
-	fmt.Println("-------- AFTER ----------")
-	runtime.ReadMemStats(&stats)
-	fmt.Printf("%+v\n", stats)
-	for i := 0; i < 10; i++ {
-		runtime.GC()
-	}
-	fmt.Println("-------- AFTER GC ----------")
-	runtime.ReadMemStats(&stats)
-	fmt.Printf("%+v\n", stats)
-	if t == v {
-		fmt.Println("to make sure vals and tree aren't GC'd")
-	}
-}
diff --git a/pkg/cache/priority_queue.go b/pkg/cache/priority_queue.go
index bfdc46a71..a7ac79090 100644
--- a/pkg/cache/priority_queue.go
+++ b/pkg/cache/priority_queue.go
@@ -24,7 +24,7 @@ const defaultDegree = 4
 // PriorityQueue queue has priority  and preempt
 type PriorityQueue struct {
 	items    map[uint64]*Entry
-	btree    *btree.BTree
+	btree    *btree.BTreeG[*Entry]
 	capacity int
 }
 
@@ -32,7 +32,7 @@ type PriorityQueue struct {
 func NewPriorityQueue(capacity int) *PriorityQueue {
 	return &PriorityQueue{
 		items:    make(map[uint64]*Entry),
-		btree:    btree.New(defaultDegree),
+		btree:    btree.NewG[*Entry](defaultDegree),
 		capacity: capacity,
 	}
 }
@@ -49,12 +49,12 @@ func (pq *PriorityQueue) Put(priority int, value PriorityQueueItem) bool {
 	if !ok {
 		entry = &Entry{Priority: priority, Value: value}
 		if pq.Len() >= pq.capacity {
-			min := pq.btree.Min()
+			min, found := pq.btree.Min()
 			// avoid to capacity equal 0
-			if min == nil || !min.Less(entry) {
+			if !found || !min.Less(entry) {
 				return false
 			}
-			pq.Remove(min.(*Entry).Value.ID())
+			pq.Remove(min.Value.ID())
 		}
 	} else if entry.Priority != priority { // delete before update
 		pq.btree.Delete(entry)
@@ -73,7 +73,7 @@ func (pq *PriorityQueue) Get(id uint64) *Entry {
 
 // Peek return the highest priority entry
 func (pq *PriorityQueue) Peek() *Entry {
-	if max, ok := pq.btree.Max().(*Entry); ok {
+	if max, ok := pq.btree.Max(); ok {
 		return max
 	}
 	return nil
@@ -81,7 +81,7 @@ func (pq *PriorityQueue) Peek() *Entry {
 
 // Tail return the lowest priority entry
 func (pq *PriorityQueue) Tail() *Entry {
-	if min, ok := pq.btree.Min().(*Entry); ok {
+	if min, ok := pq.btree.Min(); ok {
 		return min
 	}
 	return nil
@@ -91,8 +91,8 @@ func (pq *PriorityQueue) Tail() *Entry {
 func (pq *PriorityQueue) Elems() []*Entry {
 	rs := make([]*Entry, pq.Len())
 	count := 0
-	pq.btree.Descend(func(i btree.Item) bool {
-		rs[count] = i.(*Entry)
+	pq.btree.Descend(func(i *Entry) bool {
+		rs[count] = i
 		count++
 		return true
 	})
@@ -119,8 +119,8 @@ type Entry struct {
 }
 
 // Less return true if the entry has smaller priority
-func (r *Entry) Less(other btree.Item) bool {
+func (r *Entry) Less(other *Entry) bool {
 	left := r.Priority
-	right := other.(*Entry).Priority
+	right := other.Priority
 	return left > right
 }
diff --git a/server/cluster/unsafe_recovery_controller.go b/server/cluster/unsafe_recovery_controller.go
index 9c7446766..7d55c5d8f 100644
--- a/server/cluster/unsafe_recovery_controller.go
+++ b/server/cluster/unsafe_recovery_controller.go
@@ -701,17 +701,15 @@ func (u *unsafeRecoveryController) getFailedPeers(region *metapb.Region) []*meta
 	return failedPeers
 }
 
-var _ btree.Item = &regionItem{}
-
 type regionItem struct {
 	report  *pdpb.PeerReport
 	storeID uint64
 }
 
 // Less returns true if the region start key is less than the other.
-func (r *regionItem) Less(other btree.Item) bool {
+func (r *regionItem) Less(other *regionItem) bool {
 	left := r.Region().GetStartKey()
-	right := other.(*regionItem).Region().GetStartKey()
+	right := other.Region().GetStartKey()
 	return bytes.Compare(left, right) < 0
 }
 
@@ -778,13 +776,13 @@ const (
 
 type regionTree struct {
 	regions map[uint64]*regionItem
-	tree    *btree.BTree
+	tree    *btree.BTreeG[*regionItem]
 }
 
 func newRegionTree() *regionTree {
 	return &regionTree{
 		regions: make(map[uint64]*regionItem),
-		tree:    btree.New(defaultBTreeDegree),
+		tree:    btree.NewG[*regionItem](defaultBTreeDegree),
 	}
 }
 
@@ -812,8 +810,8 @@ func (t *regionTree) getOverlaps(item *regionItem) []*regionItem {
 
 	end := item.Region().GetEndKey()
 	var overlaps []*regionItem
-	t.tree.AscendGreaterOrEqual(result, func(i btree.Item) bool {
-		over := i.(*regionItem)
+	t.tree.AscendGreaterOrEqual(result, func(i *regionItem) bool {
+		over := i
 		if len(end) > 0 && bytes.Compare(end, over.Region().GetStartKey()) <= 0 {
 			return false
 		}
@@ -826,8 +824,8 @@ func (t *regionTree) getOverlaps(item *regionItem) []*regionItem {
 // find is a helper function to find an item that contains the regions start key.
 func (t *regionTree) find(item *regionItem) *regionItem {
 	var result *regionItem
-	t.tree.DescendLessOrEqual(item, func(i btree.Item) bool {
-		result = i.(*regionItem)
+	t.tree.DescendLessOrEqual(item, func(i *regionItem) bool {
+		result = i
 		return false
 	})
 
@@ -929,8 +927,8 @@ func (u *unsafeRecoveryController) generateTombstoneTiFlashLearnerPlan(newestReg
 	hasPlan := false
 
 	var err error
-	newestRegionTree.tree.Ascend(func(item btree.Item) bool {
-		region := item.(*regionItem).Region()
+	newestRegionTree.tree.Ascend(func(item *regionItem) bool {
+		region := item.Region()
 		if !u.canElectLeader(region, false) {
 			leader := u.selectLeader(peersMap, region)
 			if leader == nil {
@@ -969,9 +967,9 @@ func (u *unsafeRecoveryController) generateForceLeaderPlan(newestRegionTree *reg
 	var err error
 	// Check the regions in newest Region Tree to see if it can still elect leader
 	// considering the failed stores
-	newestRegionTree.tree.Ascend(func(item btree.Item) bool {
-		report := item.(*regionItem).report
-		region := item.(*regionItem).Region()
+	newestRegionTree.tree.Ascend(func(item *regionItem) bool {
+		report := item.report
+		region := item.Region()
 		if !u.canElectLeader(region, false) {
 			if hasForceLeader(region) {
 				// already is a force leader, skip
@@ -1040,8 +1038,8 @@ func (u *unsafeRecoveryController) generateDemoteFailedVoterPlan(newestRegionTre
 
 	// Check the regions in newest Region Tree to see if it can still elect leader
 	// considering the failed stores
-	newestRegionTree.tree.Ascend(func(item btree.Item) bool {
-		region := item.(*regionItem).Region()
+	newestRegionTree.tree.Ascend(func(item *regionItem) bool {
+		region := item.Region()
 		if !u.canElectLeader(region, false) {
 			leader := findForceLeader(peersMap, region)
 			if leader == nil {
@@ -1117,9 +1115,9 @@ func (u *unsafeRecoveryController) generateCreateEmptyRegionPlan(newestRegionTre
 	// regions that cover them and evenly distribute newly created regions among all stores.
 	lastEnd := []byte("")
 	var lastStoreID uint64
-	newestRegionTree.tree.Ascend(func(item btree.Item) bool {
-		region := item.(*regionItem).Region()
-		storeID := item.(*regionItem).storeID
+	newestRegionTree.tree.Ascend(func(item *regionItem) bool {
+		region := item.Region()
+		storeID := item.storeID
 		if !bytes.Equal(region.StartKey, lastEnd) {
 			if u.cluster.GetStore(storeID).IsTiFlash() {
 				storeID = getRandomStoreID()
diff --git a/pkg/rangetree/range_tree.go b/server/core/rangetree/range_tree.go
similarity index 78%
rename from pkg/rangetree/range_tree.go
rename to server/core/rangetree/range_tree.go
index 174e338f7..a7e63d617 100644
--- a/pkg/rangetree/range_tree.go
+++ b/server/core/rangetree/range_tree.go
@@ -20,9 +20,9 @@ import (
 	"github.com/tikv/pd/pkg/btree"
 )
 
-// RangeItem is one key range tree item.
+// RangeItem is the item of the range tree.
 type RangeItem interface {
-	btree.Item
+	Less(RangeItem) bool
 	GetStartKey() []byte
 	GetEndKey() []byte
 }
@@ -32,14 +32,14 @@ type DebrisFactory func(startKey, EndKey []byte, item RangeItem) []RangeItem
 
 // RangeTree is the tree contains RangeItems.
 type RangeTree struct {
-	tree    *btree.BTree
+	tree    *btree.BTreeG[RangeItem]
 	factory DebrisFactory
 }
 
 // NewRangeTree is the constructor of the range tree.
 func NewRangeTree(degree int, factory DebrisFactory) *RangeTree {
 	return &RangeTree{
-		tree:    btree.New(degree),
+		tree:    btree.NewG[RangeItem](degree),
 		factory: factory,
 	}
 }
@@ -74,15 +74,13 @@ func (r *RangeTree) GetOverlaps(item RangeItem) []RangeItem {
 	if result == nil {
 		result = item
 	}
-
-	var overlaps []RangeItem
 	endKey := item.GetEndKey()
-	r.tree.AscendGreaterOrEqual(result, func(i btree.Item) bool {
-		over := i.(RangeItem)
-		if len(endKey) > 0 && bytes.Compare(endKey, over.GetStartKey()) <= 0 {
+	var overlaps []RangeItem
+	r.tree.AscendGreaterOrEqual(result, func(i RangeItem) bool {
+		if len(endKey) > 0 && bytes.Compare(endKey, i.GetStartKey()) <= 0 {
 			return false
 		}
-		overlaps = append(overlaps, over)
+		overlaps = append(overlaps, i)
 		return true
 	})
 	return overlaps
@@ -91,8 +89,8 @@ func (r *RangeTree) GetOverlaps(item RangeItem) []RangeItem {
 // Find returns the range item contains the start key.
 func (r *RangeTree) Find(item RangeItem) RangeItem {
 	var result RangeItem
-	r.tree.DescendLessOrEqual(item, func(i btree.Item) bool {
-		result = i.(RangeItem)
+	r.tree.DescendLessOrEqual(item, func(i RangeItem) bool {
+		result = i
 		return false
 	})
 
@@ -110,10 +108,8 @@ func contains(item RangeItem, key []byte) bool {
 
 // Remove removes the given item and return the deleted item.
 func (r *RangeTree) Remove(item RangeItem) RangeItem {
-	if r := r.tree.Delete(item); r != nil {
-		return r.(RangeItem)
-	}
-	return nil
+	i, _ := r.tree.Delete(item)
+	return i
 }
 
 // Len returns the count of the range tree.
@@ -128,25 +124,25 @@ func (r *RangeTree) ScanRange(start RangeItem, f func(_ RangeItem) bool) {
 	if startItem == nil {
 		startItem = start
 	}
-	r.tree.AscendGreaterOrEqual(startItem, func(item btree.Item) bool {
-		return f(item.(RangeItem))
+	r.tree.AscendGreaterOrEqual(startItem, func(item RangeItem) bool {
+		return f(item)
 	})
 }
 
 // GetAdjacentItem returns the adjacent range item.
 func (r *RangeTree) GetAdjacentItem(item RangeItem) (prev RangeItem, next RangeItem) {
-	r.tree.AscendGreaterOrEqual(item, func(i btree.Item) bool {
-		if bytes.Equal(item.GetStartKey(), i.(RangeItem).GetStartKey()) {
+	r.tree.AscendGreaterOrEqual(item, func(i RangeItem) bool {
+		if bytes.Equal(item.GetStartKey(), i.GetStartKey()) {
 			return true
 		}
-		next = i.(RangeItem)
+		next = i
 		return false
 	})
-	r.tree.DescendLessOrEqual(item, func(i btree.Item) bool {
-		if bytes.Equal(item.GetStartKey(), i.(RangeItem).GetStartKey()) {
+	r.tree.DescendLessOrEqual(item, func(i RangeItem) bool {
+		if bytes.Equal(item.GetStartKey(), i.GetStartKey()) {
 			return true
 		}
-		prev = i.(RangeItem)
+		prev = i
 		return false
 	})
 	return prev, next
@@ -154,14 +150,10 @@ func (r *RangeTree) GetAdjacentItem(item RangeItem) (prev RangeItem, next RangeI
 
 // GetAt returns the given index item.
 func (r *RangeTree) GetAt(index int) RangeItem {
-	return r.tree.GetAt(index).(RangeItem)
+	return r.tree.GetAt(index)
 }
 
 // GetWithIndex returns index and item for the given item.
 func (r *RangeTree) GetWithIndex(item RangeItem) (RangeItem, int) {
-	rst, index := r.tree.GetWithIndex(item)
-	if rst == nil {
-		return nil, index
-	}
-	return rst.(RangeItem), index
+	return r.tree.GetWithIndex(item)
 }
diff --git a/server/core/region.go b/server/core/region.go
index 2c7c46c2b..ae7063c79 100644
--- a/server/core/region.go
+++ b/server/core/region.go
@@ -32,7 +32,6 @@ import (
 	"github.com/pingcap/kvproto/pkg/replication_modepb"
 	"github.com/pingcap/log"
 	"github.com/tikv/pd/pkg/logutil"
-	"github.com/tikv/pd/pkg/rangetree"
 	"github.com/tikv/pd/pkg/typeutil"
 	"go.uber.org/zap"
 )
@@ -1091,7 +1090,7 @@ func (r *RegionsInfo) RandLearnerRegions(storeID uint64, ranges []KeyRange, n in
 // GetLeader returns leader RegionInfo by storeID and regionID (now only used in test)
 func (r *RegionsInfo) GetLeader(storeID uint64, region *RegionInfo) *RegionInfo {
 	if leaders, ok := r.leaders[storeID]; ok {
-		return leaders.find(region).RegionInfo
+		return leaders.find(&regionItem{RegionInfo: region}).RegionInfo
 	}
 	return nil
 }
@@ -1099,7 +1098,7 @@ func (r *RegionsInfo) GetLeader(storeID uint64, region *RegionInfo) *RegionInfo
 // GetFollower returns follower RegionInfo by storeID and regionID (now only used in test)
 func (r *RegionsInfo) GetFollower(storeID uint64, region *RegionInfo) *RegionInfo {
 	if followers, ok := r.followers[storeID]; ok {
-		return followers.find(region).RegionInfo
+		return followers.find(&regionItem{RegionInfo: region}).RegionInfo
 	}
 	return nil
 }
@@ -1162,7 +1161,7 @@ func (r *RegionsInfo) GetRangeCount(startKey, endKey []byte) int {
 	// it returns 0 if startKey is nil.
 	_, startIndex := r.tree.tree.GetWithIndex(start)
 	var endIndex int
-	var item rangetree.RangeItem
+	var item *regionItem
 	// it should return the length of the tree if endKey is nil.
 	if len(endKey) == 0 {
 		endIndex = r.tree.tree.Len() - 1
diff --git a/server/core/region_tree.go b/server/core/region_tree.go
index 690566758..4029f8140 100644
--- a/server/core/region_tree.go
+++ b/server/core/region_tree.go
@@ -23,12 +23,9 @@ import (
 	"github.com/tikv/pd/pkg/btree"
 	"github.com/tikv/pd/pkg/errs"
 	"github.com/tikv/pd/pkg/logutil"
-	"github.com/tikv/pd/pkg/rangetree"
 	"go.uber.org/zap"
 )
 
-var _ rangetree.RangeItem = &regionItem{}
-
 type regionItem struct {
 	*RegionInfo
 }
@@ -44,9 +41,9 @@ func (r *regionItem) GetEndKey() []byte {
 }
 
 // Less returns true if the region start key is less than the other.
-func (r *regionItem) Less(other btree.Item) bool {
+func (r *regionItem) Less(other *regionItem) bool {
 	left := r.meta.StartKey
-	right := other.(*regionItem).meta.StartKey
+	right := other.meta.StartKey
 	return bytes.Compare(left, right) < 0
 }
 
@@ -60,7 +57,7 @@ const (
 )
 
 type regionTree struct {
-	tree *rangetree.RangeTree
+	tree *btree.BTreeG[*regionItem]
 	// Statistics
 	totalSize           int64
 	totalWriteBytesRate float64
@@ -68,11 +65,8 @@ type regionTree struct {
 }
 
 func newRegionTree() *regionTree {
-	factory := func(_, _ []byte, _ rangetree.RangeItem) []rangetree.RangeItem {
-		return nil
-	}
 	return &regionTree{
-		tree:                rangetree.NewRangeTree(defaultBTreeDegree, factory),
+		tree:                btree.NewG[*regionItem](defaultBTreeDegree),
 		totalSize:           0,
 		totalWriteBytesRate: 0,
 		totalWriteKeysRate:  0,
@@ -89,11 +83,35 @@ func (t *regionTree) length() int {
 // getOverlaps gets the regions which are overlapped with the specified region range.
 func (t *regionTree) getOverlaps(region *RegionInfo) []*RegionInfo {
 	item := &regionItem{RegionInfo: region}
-	result := t.tree.GetOverlaps(item)
+	result := t.overlaps(item)
 	overlaps := make([]*RegionInfo, len(result))
 	for i, r := range result {
-		overlaps[i] = r.(*regionItem).RegionInfo
+		overlaps[i] = r.RegionInfo
+	}
+	return overlaps
+}
+
+// GetOverlaps returns the range items that has some intersections with the given items.
+func (t *regionTree) overlaps(item *regionItem) []*regionItem {
+	// note that Find() gets the last item that is less or equal than the item.
+	// in the case: |_______a_______|_____b_____|___c___|
+	// new item is     |______d______|
+	// Find() will return RangeItem of item_a
+	// and both startKey of item_a and item_b are less than endKey of item_d,
+	// thus they are regarded as overlapped items.
+	result := t.find(item)
+	if result == nil {
+		result = item
 	}
+	endKey := item.GetEndKey()
+	var overlaps []*regionItem
+	t.tree.AscendGreaterOrEqual(result, func(i *regionItem) bool {
+		if len(endKey) > 0 && bytes.Compare(endKey, i.GetStartKey()) <= 0 {
+			return false
+		}
+		overlaps = append(overlaps, i)
+		return true
+	})
 	return overlaps
 }
 
@@ -107,10 +125,14 @@ func (t *regionTree) update(item *regionItem) []*RegionInfo {
 	t.totalWriteBytesRate += regionWriteBytesRate
 	t.totalWriteKeysRate += regionWriteKeysRate
 
-	overlaps := t.tree.Update(item)
+	overlaps := t.overlaps(item)
+	for _, old := range overlaps {
+		t.tree.Delete(old)
+	}
+	t.tree.ReplaceOrInsert(item)
 	result := make([]*RegionInfo, len(overlaps))
 	for i, overlap := range overlaps {
-		old := overlap.(*regionItem).RegionInfo
+		old := overlap.RegionInfo
 		result[i] = old
 		log.Debug("overlapping region",
 			zap.Uint64("region-id", old.GetID()),
@@ -146,22 +168,22 @@ func (t *regionTree) remove(region *RegionInfo) {
 		return
 	}
 	item := &regionItem{RegionInfo: region}
-	result := t.tree.Find(item)
-	if result == nil || result.(*regionItem).GetID() != region.GetID() {
+	result := t.find(item)
+	if result == nil || result.GetID() != region.GetID() {
 		return
 	}
 
-	t.totalSize -= result.(*regionItem).GetApproximateSize()
-	regionWriteBytesRate, regionWriteKeysRate := result.(*regionItem).GetWriteRate()
+	t.totalSize -= result.GetApproximateSize()
+	regionWriteBytesRate, regionWriteKeysRate := result.GetWriteRate()
 	t.totalWriteBytesRate -= regionWriteBytesRate
 	t.totalWriteKeysRate -= regionWriteKeysRate
-	t.tree.Remove(result)
+	t.tree.Delete(item)
 }
 
 // search returns a region that contains the key.
 func (t *regionTree) search(regionKey []byte) *RegionInfo {
 	region := &RegionInfo{meta: &metapb.Region{StartKey: regionKey}}
-	result := t.find(region)
+	result := t.find(&regionItem{RegionInfo: region})
 	if result == nil {
 		return nil
 	}
@@ -171,7 +193,7 @@ func (t *regionTree) search(regionKey []byte) *RegionInfo {
 // searchPrev returns the previous region of the region where the regionKey is located.
 func (t *regionTree) searchPrev(regionKey []byte) *RegionInfo {
 	curRegion := &RegionInfo{meta: &metapb.Region{StartKey: regionKey}}
-	curRegionItem := t.find(curRegion)
+	curRegionItem := t.find(&regionItem{RegionInfo: curRegion})
 	if curRegionItem == nil {
 		return nil
 	}
@@ -185,17 +207,19 @@ func (t *regionTree) searchPrev(regionKey []byte) *RegionInfo {
 	return prevRegionItem.RegionInfo
 }
 
-// find is a helper function to find an item that contains the regions start
-// key.
-func (t *regionTree) find(region *RegionInfo) *regionItem {
-	item := t.tree.Find(&regionItem{RegionInfo: region})
-	if item == nil {
+// find returns the range item contains the start key.
+func (t *regionTree) find(item *regionItem) *regionItem {
+	var result *regionItem
+	t.tree.DescendLessOrEqual(item, func(i *regionItem) bool {
+		result = i
+		return false
+	})
+
+	if result == nil || !result.Contains(item.GetStartKey()) {
 		return nil
 	}
-	if result, ok := item.(*regionItem); ok && result.Contains(region.GetStartKey()) {
-		return result
-	}
-	return nil
+
+	return result
 }
 
 // scanRage scans from the first region containing or behind the start key
@@ -203,11 +227,18 @@ func (t *regionTree) find(region *RegionInfo) *regionItem {
 func (t *regionTree) scanRange(startKey []byte, f func(*RegionInfo) bool) {
 	region := &RegionInfo{meta: &metapb.Region{StartKey: startKey}}
 	// find if there is a region with key range [s, d), s < startKey < d
-	fn := func(item rangetree.RangeItem) bool {
-		r := item.(*regionItem)
+	fn := func(item *regionItem) bool {
+		r := item
 		return f(r.RegionInfo)
 	}
-	t.tree.ScanRange(&regionItem{RegionInfo: region}, fn)
+	start := &regionItem{RegionInfo: region}
+	startItem := t.find(start)
+	if startItem == nil {
+		startItem = start
+	}
+	t.tree.AscendGreaterOrEqual(startItem, func(item *regionItem) bool {
+		return fn(item)
+	})
 }
 
 func (t *regionTree) scanRanges() []*RegionInfo {
@@ -224,14 +255,25 @@ func (t *regionTree) scanRanges() []*RegionInfo {
 
 func (t *regionTree) getAdjacentRegions(region *RegionInfo) (*regionItem, *regionItem) {
 	item := &regionItem{RegionInfo: &RegionInfo{meta: &metapb.Region{StartKey: region.GetStartKey()}}}
-	prevItem, nextItem := t.tree.GetAdjacentItem(item)
-	var prev, next *regionItem
-	if prevItem != nil {
-		prev = prevItem.(*regionItem)
-	}
-	if nextItem != nil {
-		next = nextItem.(*regionItem)
-	}
+	return t.getAdjacentItem(item)
+}
+
+// GetAdjacentItem returns the adjacent range item.
+func (t *regionTree) getAdjacentItem(item *regionItem) (prev *regionItem, next *regionItem) {
+	t.tree.AscendGreaterOrEqual(item, func(i *regionItem) bool {
+		if bytes.Equal(item.GetStartKey(), i.GetStartKey()) {
+			return true
+		}
+		next = i
+		return false
+	})
+	t.tree.DescendLessOrEqual(item, func(i *regionItem) bool {
+		if bytes.Equal(item.GetStartKey(), i.GetStartKey()) {
+			return true
+		}
+		prev = i
+		return false
+	})
 	return prev, next
 }
 
@@ -258,7 +300,7 @@ func (t *regionTree) RandomRegion(ranges []KeyRange) *RegionInfo {
 
 		// Consider that the item in the tree may not be continuous,
 		// we need to check if the previous item contains the key.
-		if startIndex != 0 && startRegion == nil && t.tree.GetAt(startIndex-1).(*regionItem).Contains(startKey) {
+		if startIndex != 0 && startRegion == nil && t.tree.GetAt(startIndex-1).Contains(startKey) {
 			startIndex--
 		}
 
@@ -272,7 +314,7 @@ func (t *regionTree) RandomRegion(ranges []KeyRange) *RegionInfo {
 			continue
 		}
 		index := rand.Intn(endIndex-startIndex) + startIndex
-		region := t.tree.GetAt(index).(*regionItem).RegionInfo
+		region := t.tree.GetAt(index).RegionInfo
 		if region.isInvolved(startKey, endKey) {
 			return region
 		}
diff --git a/server/statistics/buckets/bucket_stat_informer.go b/server/statistics/buckets/bucket_stat_informer.go
index 87175e41d..10a14258f 100644
--- a/server/statistics/buckets/bucket_stat_informer.go
+++ b/server/statistics/buckets/bucket_stat_informer.go
@@ -18,10 +18,10 @@ import (
 	"bytes"
 	"fmt"
 
-	"github.com/tikv/pd/pkg/btree"
 	"github.com/tikv/pd/pkg/keyutil"
 	"github.com/tikv/pd/pkg/slice"
 	"github.com/tikv/pd/server/core"
+	"github.com/tikv/pd/server/core/rangetree"
 	"github.com/tikv/pd/server/statistics"
 )
 
@@ -95,7 +95,7 @@ func (b *BucketTreeItem) String() string {
 }
 
 // Less returns true if the start key is less than the other.
-func (b *BucketTreeItem) Less(than btree.Item) bool {
+func (b *BucketTreeItem) Less(than rangetree.RangeItem) bool {
 	return bytes.Compare(b.startKey, than.(*BucketTreeItem).startKey) < 0
 }
 
diff --git a/server/statistics/buckets/hot_bucket_cache.go b/server/statistics/buckets/hot_bucket_cache.go
index 8b1ed0b45..5fe603216 100644
--- a/server/statistics/buckets/hot_bucket_cache.go
+++ b/server/statistics/buckets/hot_bucket_cache.go
@@ -23,7 +23,7 @@ import (
 	"github.com/pingcap/log"
 	"github.com/tikv/pd/pkg/keyutil"
 	"github.com/tikv/pd/pkg/logutil"
-	"github.com/tikv/pd/pkg/rangetree"
+	"github.com/tikv/pd/server/core/rangetree"
 	"go.uber.org/zap"
 )
 


Test patch:
diff --git a/pkg/btree/btree_test.go b/pkg/btree/btree_generic_test.go
similarity index 64%
rename from pkg/btree/btree_test.go
rename to pkg/btree/btree_generic_test.go
index 647885b18..228269056 100644
--- a/pkg/btree/btree_test.go
+++ b/pkg/btree/btree_generic_test.go
@@ -1,4 +1,18 @@
-// Copyright 2014 Google Inc.
+// Copyright 2014-2022 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Copyright 2022 TiKV Project Authors.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
@@ -22,17 +36,10 @@ import (
 	"sort"
 	"sync"
 	"testing"
-	"time"
 )
 
-func init() {
-	seed := time.Now().Unix()
-	fmt.Println(seed)
-	rand.Seed(seed)
-}
-
 // perm returns a random permutation of n Int items in the range [0, n).
-func perm(n int) (out []Item) {
+func perm(n int) (out []Int) {
 	for _, v := range rand.Perm(n) {
 		out = append(out, Int(v))
 	}
@@ -40,7 +47,7 @@ func perm(n int) (out []Item) {
 }
 
 // rang returns an ordered list of Int items in the range [0, n).
-func rang(n int) (out []Item) {
+func rang(n int) (out []Int) {
 	for i := 0; i < n; i++ {
 		out = append(out, Int(i))
 	}
@@ -48,8 +55,8 @@ func rang(n int) (out []Item) {
 }
 
 // all extracts all items from a tree in order as a slice.
-func all(t *BTree) (out []Item) {
-	t.Ascend(func(a Item) bool {
+func all[T Item[T]](t *BTreeG[T]) (out []T) {
+	t.Ascend(func(a T) bool {
 		out = append(out, a)
 		return true
 	})
@@ -57,7 +64,7 @@ func all(t *BTree) (out []Item) {
 }
 
 // rangerev returns a reversed ordered list of Int items in the range [0, n).
-func rangrev(n int) (out []Item) {
+func rangrev(n int) (out []Int) {
 	for i := n - 1; i >= 0; i-- {
 		out = append(out, Int(i))
 	}
@@ -65,8 +72,8 @@ func rangrev(n int) (out []Item) {
 }
 
 // allrev extracts all items from a tree in reverse order as a slice.
-func allrev(t *BTree) (out []Item) {
-	t.Descend(func(a Item) bool {
+func allrev[T Item[T]](t *BTreeG[T]) (out []T) {
+	t.Descend(func(a T) bool {
 		out = append(out, a)
 		return true
 	})
@@ -79,53 +86,57 @@ func assertEq(t *testing.T, desc string, got, need interface{}) {
 	}
 }
 
+var btreeDegree = flag.Int("degree", 32, "B-Tree degree")
+
 func TestBTreeSizeInfo(t *testing.T) {
-	tr := New(*btreeDegree)
-	const maxElt = 10000
-	elements := perm(maxElt)
-	// insert 0..maxElt
-	for _, elt := range elements {
-		tr.ReplaceOrInsert(elt)
+	tr := NewG[Int](*btreeDegree)
+	const treeSize = 10000
+	for _, item := range perm(treeSize) {
+		tr.ReplaceOrInsert(item)
 		assertEq(t, "root length", tr.getRootLength(), tr.Len())
-		assertEq(t, "check min", tr.GetAt(0), tr.Min())
-		assertEq(t, "check max", tr.GetAt(tr.Len()-1), tr.Max())
+		min, _ := tr.Min()
+		assertEq(t, "check min", tr.GetAt(0), min)
+		max, _ := tr.Max()
+		assertEq(t, "check max", tr.GetAt(tr.Len()-1), max)
 	}
-	for k := 0; k < maxElt; k++ {
+	for k := 0; k < treeSize; k++ {
 		assertEq(t, "get k-th", tr.GetAt(k), Int(k))
 	}
-	for x := 0; x < maxElt; x++ {
-		y, rk := tr.GetWithIndex(Int(x))
-		assertEq(t, "get", y, Int(x))
-		assertEq(t, "get rank", rk, x)
+	for x := Int(0); x < treeSize; x++ {
+		y, rk := tr.GetWithIndex(x)
+		assertEq(t, "get", y, x)
+		assertEq(t, "get rank", rk, int(x))
 	}
 
 	// get rank of maxElt + 1
 	{
-		y, rk := tr.GetWithIndex(Int(maxElt + 1))
-		assertEq(t, "get max+1", y, nil)
+		y, rk := tr.GetWithIndex(treeSize + 1)
+		assertEq(t, "get max+1", y, Int(0))
 		assertEq(t, "get max+1 rank", rk, tr.Len())
 	}
 
 	// delete x if x % 3 == 0
-	for _, elt := range elements {
-		if int(elt.(Int))%3 != 0 {
-			tr.Delete(elt)
+	for _, item := range perm(treeSize) {
+		if item%3 != 0 {
+			tr.Delete(item)
 		}
 		assertEq(t, "after delete root length", tr.getRootLength(), tr.Len())
-		assertEq(t, "after delete check min", tr.GetAt(0), tr.Min())
-		assertEq(t, "after delete check max", tr.GetAt(tr.Len()-1), tr.Max())
+		min, _ := tr.Min()
+		assertEq(t, "after delete check min", tr.GetAt(0), min)
+		max, _ := tr.Max()
+		assertEq(t, "after delete check max", tr.GetAt(tr.Len()-1), max)
 	}
-	for k := 0; k < maxElt/3; k++ {
+	for k := 0; k < treeSize/3; k++ {
 		assertEq(t, "after delete get k-th", tr.GetAt(k), Int(3*k))
 	}
-	for x := 0; x < maxElt; x++ {
-		y, rk := tr.GetWithIndex(Int(x))
+	for x := Int(0); x < treeSize; x++ {
+		y, rk := tr.GetWithIndex(x)
 		if x%3 == 0 {
-			assertEq(t, "after delete get", y, Int(x))
-			assertEq(t, "after delete get rank", rk, x/3)
+			assertEq(t, "after delete get", y, x)
+			assertEq(t, "after delete get rank", rk, int(x/3))
 		} else {
-			assertEq(t, "after delete get nil", y, nil)
-			assertEq(t, "after delete get nil rank", rk, x/3+1)
+			assertEq(t, "after delete get nil", y, Int(0))
+			assertEq(t, "after delete get nil rank", rk, int(x/3+1))
 		}
 	}
 
@@ -133,51 +144,51 @@ func TestBTreeSizeInfo(t *testing.T) {
 	for tr.Len() > 100 {
 		tr.DeleteMax()
 		assertEq(t, "delete max root length", tr.getRootLength(), tr.Len())
-		assertEq(t, "delete max check min", tr.GetAt(0), tr.Min())
-		assertEq(t, "delete max check max", tr.GetAt(tr.Len()-1), tr.Max())
+		min, _ := tr.Min()
+		assertEq(t, "delete max check min", tr.GetAt(0), min)
+		max, _ := tr.Max()
+		assertEq(t, "delete max check max", tr.GetAt(tr.Len()-1), max)
 	}
-	for k := 0; k < maxElt/3 && k < 100; k++ {
+	for k := 0; k < treeSize/3 && k < 100; k++ {
 		assertEq(t, "delete max get k-th", tr.GetAt(k), Int(3*k))
 	}
-	for x := 0; x < maxElt && x < 300; x++ {
-		y, rk := tr.GetWithIndex(Int(x))
+	for x := Int(0); x < treeSize && x < 300; x++ {
+		y, rk := tr.GetWithIndex(x)
 		if x%3 == 0 {
-			assertEq(t, "delete max get", y, Int(x))
-			assertEq(t, "delete max get rank", rk, x/3)
+			assertEq(t, "delete max get", y, x)
+			assertEq(t, "delete max get rank", rk, int(x/3))
 		} else {
-			assertEq(t, "delete max get nil", y, nil)
-			assertEq(t, "delete max get nil rank", rk, x/3+1)
+			assertEq(t, "delete max get nil", y, Int(0))
+			assertEq(t, "delete max get nil rank", rk, int(x/3+1))
 		}
 	}
 }
 
-var btreeDegree = flag.Int("degree", 32, "B-Tree degree")
-
-func TestBTree(t *testing.T) {
-	tr := New(*btreeDegree)
+func TestBTreeG(t *testing.T) {
+	tr := NewG[Int](*btreeDegree)
 	const treeSize = 10000
 	for i := 0; i < 10; i++ {
-		if min := tr.Min(); min != nil {
+		if min, found := tr.Min(); found {
 			t.Fatalf("empty min, got %+v", min)
 		}
-		if max := tr.Max(); max != nil {
+		if max, found := tr.Max(); found {
 			t.Fatalf("empty max, got %+v", max)
 		}
 		for _, item := range perm(treeSize) {
-			if x := tr.ReplaceOrInsert(item); x != nil {
+			if _, found := tr.ReplaceOrInsert(item); found {
 				t.Fatal("insert found item", item)
 			}
 		}
 		for _, item := range perm(treeSize) {
-			if x := tr.ReplaceOrInsert(item); x == nil {
+			if _, found := tr.ReplaceOrInsert(item); !found {
 				t.Fatal("insert didn't find item", item)
 			}
 		}
-		if min, want := tr.Min(), Item(Int(0)); min != want {
-			t.Fatalf("min: want %+v, got %+v", want, min)
+		if min, found := tr.Min(); !found || min != Int(0) {
+			t.Fatalf("min: want %+v, got %+v", Int(0), min)
 		}
-		if max, want := tr.Max(), Item(Int(treeSize-1)); max != want {
-			t.Fatalf("max: want %+v, got %+v", want, max)
+		if max, found := tr.Max(); !found || max != Int(treeSize-1) {
+			t.Fatalf("max: want %+v, got %+v", Int(treeSize-1), max)
 		}
 		got := all(tr)
 		want := rang(treeSize)
@@ -192,7 +203,7 @@ func TestBTree(t *testing.T) {
 		}
 
 		for _, item := range perm(treeSize) {
-			if x := tr.Delete(item); x == nil {
+			if _, found := tr.Delete(item); !found {
 				t.Fatalf("didn't find %v", item)
 			}
 		}
@@ -202,45 +213,55 @@ func TestBTree(t *testing.T) {
 	}
 }
 
-func ExampleBTree() {
-	tr := New(*btreeDegree)
+func ExampleBTreeG() {
+	tr := NewG[Int](*btreeDegree)
 	for i := Int(0); i < 10; i++ {
 		tr.ReplaceOrInsert(i)
 	}
 	fmt.Println("len:       ", tr.Len())
-	fmt.Println("get3:      ", tr.Get(Int(3)))
-	fmt.Println("get100:    ", tr.Get(Int(100)))
-	fmt.Println("del4:      ", tr.Delete(Int(4)))
-	fmt.Println("del100:    ", tr.Delete(Int(100)))
-	fmt.Println("replace5:  ", tr.ReplaceOrInsert(Int(5)))
-	fmt.Println("replace100:", tr.ReplaceOrInsert(Int(100)))
-	fmt.Println("min:       ", tr.Min())
-	fmt.Println("delmin:    ", tr.DeleteMin())
-	fmt.Println("max:       ", tr.Max())
-	fmt.Println("delmax:    ", tr.DeleteMax())
+	v, ok := tr.Get(3)
+	fmt.Println("get3:      ", v, ok)
+	v, ok = tr.Get(100)
+	fmt.Println("get100:    ", v, ok)
+	v, ok = tr.Delete(4)
+	fmt.Println("del4:      ", v, ok)
+	v, ok = tr.Delete(100)
+	fmt.Println("del100:    ", v, ok)
+	v, ok = tr.ReplaceOrInsert(5)
+	fmt.Println("replace5:  ", v, ok)
+	v, ok = tr.ReplaceOrInsert(100)
+	fmt.Println("replace100:", v, ok)
+	v, ok = tr.Min()
+	fmt.Println("min:       ", v, ok)
+	v, ok = tr.DeleteMin()
+	fmt.Println("delmin:    ", v, ok)
+	v, ok = tr.Max()
+	fmt.Println("max:       ", v, ok)
+	v, ok = tr.DeleteMax()
+	fmt.Println("delmax:    ", v, ok)
 	fmt.Println("len:       ", tr.Len())
 	// Output:
 	// len:        10
-	// get3:       3
-	// get100:     <nil>
-	// del4:       4
-	// del100:     <nil>
-	// replace5:   5
-	// replace100: <nil>
-	// min:        0
-	// delmin:     0
-	// max:        100
-	// delmax:     100
+	// get3:       3 true
+	// get100:     0 false
+	// del4:       4 true
+	// del100:     0 false
+	// replace5:   5 true
+	// replace100: 0 false
+	// min:        0 true
+	// delmin:     0 true
+	// max:        100 true
+	// delmax:     100 true
 	// len:        8
 }
 
-func TestDeleteMin(t *testing.T) {
-	tr := New(3)
+func TestDeleteMinG(t *testing.T) {
+	tr := NewG[Int](3)
 	for _, v := range perm(100) {
 		tr.ReplaceOrInsert(v)
 	}
-	var got []Item
-	for v := tr.DeleteMin(); v != nil; v = tr.DeleteMin() {
+	var got []Int
+	for v, found := tr.DeleteMin(); found; v, found = tr.DeleteMin() {
 		got = append(got, v)
 	}
 	if want := rang(100); !reflect.DeepEqual(got, want) {
@@ -248,13 +269,13 @@ func TestDeleteMin(t *testing.T) {
 	}
 }
 
-func TestDeleteMax(t *testing.T) {
-	tr := New(3)
+func TestDeleteMaxG(t *testing.T) {
+	tr := NewG[Int](3)
 	for _, v := range perm(100) {
 		tr.ReplaceOrInsert(v)
 	}
-	var got []Item
-	for v := tr.DeleteMax(); v != nil; v = tr.DeleteMax() {
+	var got []Int
+	for v, found := tr.DeleteMax(); found; v, found = tr.DeleteMax() {
 		got = append(got, v)
 	}
 	// Reverse our list.
@@ -266,13 +287,13 @@ func TestDeleteMax(t *testing.T) {
 	}
 }
 
-func TestAscendRange(t *testing.T) {
-	tr := New(2)
+func TestAscendRangeG(t *testing.T) {
+	tr := NewG[Int](2)
 	for _, v := range perm(100) {
 		tr.ReplaceOrInsert(v)
 	}
-	var got []Item
-	tr.AscendRange(Int(40), Int(60), func(a Item) bool {
+	var got []Int
+	tr.AscendRange(Int(40), Int(60), func(a Int) bool {
 		got = append(got, a)
 		return true
 	})
@@ -280,8 +301,8 @@ func TestAscendRange(t *testing.T) {
 		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
 	}
 	got = got[:0]
-	tr.AscendRange(Int(40), Int(60), func(a Item) bool {
-		if a.(Int) > 50 {
+	tr.AscendRange(Int(40), Int(60), func(a Int) bool {
+		if a > 50 {
 			return false
 		}
 		got = append(got, a)
@@ -292,13 +313,13 @@ func TestAscendRange(t *testing.T) {
 	}
 }
 
-func TestDescendRange(t *testing.T) {
-	tr := New(2)
+func TestDescendRangeG(t *testing.T) {
+	tr := NewG[Int](2)
 	for _, v := range perm(100) {
 		tr.ReplaceOrInsert(v)
 	}
-	var got []Item
-	tr.DescendRange(Int(60), Int(40), func(a Item) bool {
+	var got []Int
+	tr.DescendRange(Int(60), Int(40), func(a Int) bool {
 		got = append(got, a)
 		return true
 	})
@@ -306,8 +327,8 @@ func TestDescendRange(t *testing.T) {
 		t.Fatalf("descendrange:\n got: %v\nwant: %v", got, want)
 	}
 	got = got[:0]
-	tr.DescendRange(Int(60), Int(40), func(a Item) bool {
-		if a.(Int) < 50 {
+	tr.DescendRange(Int(60), Int(40), func(a Int) bool {
+		if a < 50 {
 			return false
 		}
 		got = append(got, a)
@@ -317,13 +338,14 @@ func TestDescendRange(t *testing.T) {
 		t.Fatalf("descendrange:\n got: %v\nwant: %v", got, want)
 	}
 }
-func TestAscendLessThan(t *testing.T) {
-	tr := New(*btreeDegree)
+
+func TestAscendLessThanG(t *testing.T) {
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range perm(100) {
 		tr.ReplaceOrInsert(v)
 	}
-	var got []Item
-	tr.AscendLessThan(Int(60), func(a Item) bool {
+	var got []Int
+	tr.AscendLessThan(Int(60), func(a Int) bool {
 		got = append(got, a)
 		return true
 	})
@@ -331,8 +353,8 @@ func TestAscendLessThan(t *testing.T) {
 		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
 	}
 	got = got[:0]
-	tr.AscendLessThan(Int(60), func(a Item) bool {
-		if a.(Int) > 50 {
+	tr.AscendLessThan(Int(60), func(a Int) bool {
+		if a > 50 {
 			return false
 		}
 		got = append(got, a)
@@ -343,13 +365,13 @@ func TestAscendLessThan(t *testing.T) {
 	}
 }
 
-func TestDescendLessOrEqual(t *testing.T) {
-	tr := New(*btreeDegree)
+func TestDescendLessOrEqualG(t *testing.T) {
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range perm(100) {
 		tr.ReplaceOrInsert(v)
 	}
-	var got []Item
-	tr.DescendLessOrEqual(Int(40), func(a Item) bool {
+	var got []Int
+	tr.DescendLessOrEqual(Int(40), func(a Int) bool {
 		got = append(got, a)
 		return true
 	})
@@ -357,8 +379,8 @@ func TestDescendLessOrEqual(t *testing.T) {
 		t.Fatalf("descendlessorequal:\n got: %v\nwant: %v", got, want)
 	}
 	got = got[:0]
-	tr.DescendLessOrEqual(Int(60), func(a Item) bool {
-		if a.(Int) < 50 {
+	tr.DescendLessOrEqual(Int(60), func(a Int) bool {
+		if a < 50 {
 			return false
 		}
 		got = append(got, a)
@@ -368,13 +390,14 @@ func TestDescendLessOrEqual(t *testing.T) {
 		t.Fatalf("descendlessorequal:\n got: %v\nwant: %v", got, want)
 	}
 }
-func TestAscendGreaterOrEqual(t *testing.T) {
-	tr := New(*btreeDegree)
+
+func TestAscendGreaterOrEqualG(t *testing.T) {
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range perm(100) {
 		tr.ReplaceOrInsert(v)
 	}
-	var got []Item
-	tr.AscendGreaterOrEqual(Int(40), func(a Item) bool {
+	var got []Int
+	tr.AscendGreaterOrEqual(Int(40), func(a Int) bool {
 		got = append(got, a)
 		return true
 	})
@@ -382,8 +405,8 @@ func TestAscendGreaterOrEqual(t *testing.T) {
 		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
 	}
 	got = got[:0]
-	tr.AscendGreaterOrEqual(Int(40), func(a Item) bool {
-		if a.(Int) > 50 {
+	tr.AscendGreaterOrEqual(Int(40), func(a Int) bool {
+		if a > 50 {
 			return false
 		}
 		got = append(got, a)
@@ -394,13 +417,13 @@ func TestAscendGreaterOrEqual(t *testing.T) {
 	}
 }
 
-func TestDescendGreaterThan(t *testing.T) {
-	tr := New(*btreeDegree)
+func TestDescendGreaterThanG(t *testing.T) {
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range perm(100) {
 		tr.ReplaceOrInsert(v)
 	}
-	var got []Item
-	tr.DescendGreaterThan(Int(40), func(a Item) bool {
+	var got []Int
+	tr.DescendGreaterThan(Int(40), func(a Int) bool {
 		got = append(got, a)
 		return true
 	})
@@ -408,8 +431,8 @@ func TestDescendGreaterThan(t *testing.T) {
 		t.Fatalf("descendgreaterthan:\n got: %v\nwant: %v", got, want)
 	}
 	got = got[:0]
-	tr.DescendGreaterThan(Int(40), func(a Item) bool {
-		if a.(Int) < 50 {
+	tr.DescendGreaterThan(Int(40), func(a Int) bool {
+		if a < 50 {
 			return false
 		}
 		got = append(got, a)
@@ -428,7 +451,7 @@ func BenchmarkInsert(b *testing.B) {
 	b.StartTimer()
 	i := 0
 	for i < b.N {
-		tr := New(*btreeDegree)
+		tr := NewG[Int](*btreeDegree)
 		for _, item := range insertP {
 			tr.ReplaceOrInsert(item)
 			i++
@@ -443,21 +466,21 @@ func BenchmarkSeek(b *testing.B) {
 	b.StopTimer()
 	size := 100000
 	insertP := perm(size)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, item := range insertP {
 		tr.ReplaceOrInsert(item)
 	}
 	b.StartTimer()
 
 	for i := 0; i < b.N; i++ {
-		tr.AscendGreaterOrEqual(Int(i%size), func(i Item) bool { return false })
+		tr.AscendGreaterOrEqual(Int(i%size), func(i Int) bool { return false })
 	}
 }
 
 func BenchmarkDeleteInsert(b *testing.B) {
 	b.StopTimer()
 	insertP := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, item := range insertP {
 		tr.ReplaceOrInsert(item)
 	}
@@ -471,7 +494,7 @@ func BenchmarkDeleteInsert(b *testing.B) {
 func BenchmarkDeleteInsertCloneOnce(b *testing.B) {
 	b.StopTimer()
 	insertP := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, item := range insertP {
 		tr.ReplaceOrInsert(item)
 	}
@@ -486,7 +509,7 @@ func BenchmarkDeleteInsertCloneOnce(b *testing.B) {
 func BenchmarkDeleteInsertCloneEachTime(b *testing.B) {
 	b.StopTimer()
 	insertP := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, item := range insertP {
 		tr.ReplaceOrInsert(item)
 	}
@@ -506,7 +529,7 @@ func BenchmarkDelete(b *testing.B) {
 	i := 0
 	for i < b.N {
 		b.StopTimer()
-		tr := New(*btreeDegree)
+		tr := NewG[Int](*btreeDegree)
 		for _, v := range insertP {
 			tr.ReplaceOrInsert(v)
 		}
@@ -532,7 +555,7 @@ func BenchmarkGet(b *testing.B) {
 	i := 0
 	for i < b.N {
 		b.StopTimer()
-		tr := New(*btreeDegree)
+		tr := NewG[Int](*btreeDegree)
 		for _, v := range insertP {
 			tr.ReplaceOrInsert(v)
 		}
@@ -555,7 +578,7 @@ func BenchmarkGetCloneEachTime(b *testing.B) {
 	i := 0
 	for i < b.N {
 		b.StopTimer()
-		tr := New(*btreeDegree)
+		tr := NewG[Int](*btreeDegree)
 		for _, v := range insertP {
 			tr.ReplaceOrInsert(v)
 		}
@@ -571,14 +594,14 @@ func BenchmarkGetCloneEachTime(b *testing.B) {
 	}
 }
 
-type byInts []Item
+type byInts []Int
 
 func (a byInts) Len() int {
 	return len(a)
 }
 
 func (a byInts) Less(i, j int) bool {
-	return a[i].(Int) < a[j].(Int)
+	return a[i] < a[j]
 }
 
 func (a byInts) Swap(i, j int) {
@@ -587,7 +610,7 @@ func (a byInts) Swap(i, j int) {
 
 func BenchmarkAscend(b *testing.B) {
 	arr := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range arr {
 		tr.ReplaceOrInsert(v)
 	}
@@ -595,9 +618,9 @@ func BenchmarkAscend(b *testing.B) {
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
 		j := 0
-		tr.Ascend(func(item Item) bool {
-			if item.(Int) != arr[j].(Int) {
-				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
+		tr.Ascend(func(item Int) bool {
+			if item != arr[j] {
+				b.Fatalf("mismatch: expected: %v, got %v", arr[j], item)
 			}
 			j++
 			return true
@@ -607,7 +630,7 @@ func BenchmarkAscend(b *testing.B) {
 
 func BenchmarkDescend(b *testing.B) {
 	arr := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range arr {
 		tr.ReplaceOrInsert(v)
 	}
@@ -615,18 +638,19 @@ func BenchmarkDescend(b *testing.B) {
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
 		j := len(arr) - 1
-		tr.Descend(func(item Item) bool {
-			if item.(Int) != arr[j].(Int) {
-				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
+		tr.Descend(func(item Int) bool {
+			if item != arr[j] {
+				b.Fatalf("mismatch: expected: %v, got %v", arr[j], item)
 			}
 			j--
 			return true
 		})
 	}
 }
+
 func BenchmarkAscendRange(b *testing.B) {
 	arr := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range arr {
 		tr.ReplaceOrInsert(v)
 	}
@@ -634,9 +658,9 @@ func BenchmarkAscendRange(b *testing.B) {
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
 		j := 100
-		tr.AscendRange(Int(100), arr[len(arr)-100], func(item Item) bool {
-			if item.(Int) != arr[j].(Int) {
-				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
+		tr.AscendRange(Int(100), arr[len(arr)-100], func(item Int) bool {
+			if item != arr[j] {
+				b.Fatalf("mismatch: expected: %v, got %v", arr[j], item)
 			}
 			j++
 			return true
@@ -649,7 +673,7 @@ func BenchmarkAscendRange(b *testing.B) {
 
 func BenchmarkDescendRange(b *testing.B) {
 	arr := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range arr {
 		tr.ReplaceOrInsert(v)
 	}
@@ -657,9 +681,9 @@ func BenchmarkDescendRange(b *testing.B) {
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
 		j := len(arr) - 100
-		tr.DescendRange(arr[len(arr)-100], Int(100), func(item Item) bool {
-			if item.(Int) != arr[j].(Int) {
-				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
+		tr.DescendRange(arr[len(arr)-100], Int(100), func(item Int) bool {
+			if item != arr[j] {
+				b.Fatalf("mismatch: expected: %v, got %v", arr[j], item)
 			}
 			j--
 			return true
@@ -669,9 +693,10 @@ func BenchmarkDescendRange(b *testing.B) {
 		}
 	}
 }
+
 func BenchmarkAscendGreaterOrEqual(b *testing.B) {
 	arr := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range arr {
 		tr.ReplaceOrInsert(v)
 	}
@@ -680,9 +705,9 @@ func BenchmarkAscendGreaterOrEqual(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		j := 100
 		k := 0
-		tr.AscendGreaterOrEqual(Int(100), func(item Item) bool {
-			if item.(Int) != arr[j].(Int) {
-				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
+		tr.AscendGreaterOrEqual(Int(100), func(item Int) bool {
+			if item != arr[j] {
+				b.Fatalf("mismatch: expected: %v, got %v", arr[j], item)
 			}
 			j++
 			k++
@@ -696,9 +721,10 @@ func BenchmarkAscendGreaterOrEqual(b *testing.B) {
 		}
 	}
 }
+
 func BenchmarkDescendLessOrEqual(b *testing.B) {
 	arr := perm(benchmarkTreeSize)
-	tr := New(*btreeDegree)
+	tr := NewG[Int](*btreeDegree)
 	for _, v := range arr {
 		tr.ReplaceOrInsert(v)
 	}
@@ -707,9 +733,9 @@ func BenchmarkDescendLessOrEqual(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		j := len(arr) - 100
 		k := len(arr)
-		tr.DescendLessOrEqual(arr[len(arr)-100], func(item Item) bool {
-			if item.(Int) != arr[j].(Int) {
-				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
+		tr.DescendLessOrEqual(arr[len(arr)-100], func(item Int) bool {
+			if item != arr[j] {
+				b.Fatalf("mismatch: expected: %v, got %v", arr[j], item)
 			}
 			j--
 			k--
@@ -726,7 +752,7 @@ func BenchmarkDescendLessOrEqual(b *testing.B) {
 
 const cloneTestSize = 10000
 
-func cloneTest(t *testing.T, b *BTree, start int, p []Item, wg *sync.WaitGroup, trees *[]*BTree, lock *sync.Mutex) {
+func cloneTestG[T Item[T]](t *testing.T, b *BTreeG[T], start int, p []T, wg *sync.WaitGroup, trees *[]*BTreeG[T], lock *sync.Mutex) {
 	t.Logf("Starting new clone at %v", start)
 	lock.Lock()
 	*trees = append(*trees, b)
@@ -735,19 +761,19 @@ func cloneTest(t *testing.T, b *BTree, start int, p []Item, wg *sync.WaitGroup,
 		b.ReplaceOrInsert(p[i])
 		if i%(cloneTestSize/5) == 0 {
 			wg.Add(1)
-			go cloneTest(t, b.Clone(), i+1, p, wg, trees, lock)
+			go cloneTestG(t, b.Clone(), i+1, p, wg, trees, lock)
 		}
 	}
 	wg.Done()
 }
 
-func TestCloneConcurrentOperations(t *testing.T) {
-	b := New(*btreeDegree)
-	trees := []*BTree{}
+func TestCloneConcurrentOperationsG(t *testing.T) {
+	b := NewG[Int](*btreeDegree)
+	trees := []*BTreeG[Int]{}
 	p := perm(cloneTestSize)
 	var wg sync.WaitGroup
 	wg.Add(1)
-	go cloneTest(t, b, 0, p, &wg, &trees, &sync.Mutex{})
+	go cloneTestG(t, b, 0, p, &wg, &trees, &sync.Mutex{})
 	wg.Wait()
 	want := rang(cloneTestSize)
 	t.Logf("Starting equality checks on %d trees", len(trees))
@@ -771,7 +797,7 @@ func TestCloneConcurrentOperations(t *testing.T) {
 	wg.Wait()
 	t.Log("Checking all values again")
 	for i, tree := range trees {
-		var wantpart []Item
+		var wantpart []Int
 		if i < len(trees)/2 {
 			wantpart = want[:cloneTestSize/2]
 		} else {
@@ -787,55 +813,55 @@ func BenchmarkDeleteAndRestore(b *testing.B) {
 	items := perm(16392)
 	b.ResetTimer()
 	b.Run(`CopyBigFreeList`, func(b *testing.B) {
-		fl := NewFreeList(16392)
-		tr := NewWithFreeList(*btreeDegree, fl)
+		fl := NewFreeListG[Int](16392)
+		tr := NewWithFreeListG[Int](*btreeDegree, fl)
 		for _, v := range items {
 			tr.ReplaceOrInsert(v)
 		}
 		b.ReportAllocs()
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
-			dels := make([]Item, 0, tr.Len())
-			tr.Ascend(func(b Item) bool {
+			dels := make([]Int, 0, tr.Len())
+			tr.Ascend(ItemIteratorG[Int](func(b Int) bool {
 				dels = append(dels, b)
 				return true
-			})
+			}))
 			for _, del := range dels {
 				tr.Delete(del)
 			}
 			// tr is now empty, we make a new empty copy of it.
-			tr = NewWithFreeList(*btreeDegree, fl)
+			tr = NewWithFreeListG[Int](*btreeDegree, fl)
 			for _, v := range items {
 				tr.ReplaceOrInsert(v)
 			}
 		}
 	})
 	b.Run(`Copy`, func(b *testing.B) {
-		tr := New(*btreeDegree)
+		tr := NewG[Int](*btreeDegree)
 		for _, v := range items {
 			tr.ReplaceOrInsert(v)
 		}
 		b.ReportAllocs()
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
-			dels := make([]Item, 0, tr.Len())
-			tr.Ascend(func(b Item) bool {
+			dels := make([]Int, 0, tr.Len())
+			tr.Ascend(ItemIteratorG[Int](func(b Int) bool {
 				dels = append(dels, b)
 				return true
-			})
+			}))
 			for _, del := range dels {
 				tr.Delete(del)
 			}
 			// tr is now empty, we make a new empty copy of it.
-			tr = New(*btreeDegree)
+			tr = NewG[Int](*btreeDegree)
 			for _, v := range items {
 				tr.ReplaceOrInsert(v)
 			}
 		}
 	})
 	b.Run(`ClearBigFreelist`, func(b *testing.B) {
-		fl := NewFreeList(16392)
-		tr := NewWithFreeList(*btreeDegree, fl)
+		fl := NewFreeListG[Int](16392)
+		tr := NewWithFreeListG[Int](*btreeDegree, fl)
 		for _, v := range items {
 			tr.ReplaceOrInsert(v)
 		}
@@ -849,7 +875,7 @@ func BenchmarkDeleteAndRestore(b *testing.B) {
 		}
 	})
 	b.Run(`Clear`, func(b *testing.B) {
-		tr := New(*btreeDegree)
+		tr := NewG[Int](*btreeDegree)
 		for _, v := range items {
 			tr.ReplaceOrInsert(v)
 		}
diff --git a/pkg/rangetree/range_tree_test.go b/server/core/rangetree/range_tree_test.go
similarity index 96%
rename from pkg/rangetree/range_tree_test.go
rename to server/core/rangetree/range_tree_test.go
index 9e8e7e9dc..6bbd68609 100644
--- a/pkg/rangetree/range_tree_test.go
+++ b/server/core/rangetree/range_tree_test.go
@@ -19,7 +19,6 @@ import (
 	"testing"
 
 	"github.com/stretchr/testify/require"
-	"github.com/tikv/pd/pkg/btree"
 )
 
 type simpleBucketItem struct {
@@ -35,8 +34,8 @@ func newSimpleBucketItem(startKey, endKey []byte) *simpleBucketItem {
 }
 
 // Less returns true if the start key of the item is less than the start key of the argument.
-func (s *simpleBucketItem) Less(than btree.Item) bool {
-	return bytes.Compare(s.GetStartKey(), than.(RangeItem).GetStartKey()) < 0
+func (s *simpleBucketItem) Less(than RangeItem) bool {
+	return bytes.Compare(s.GetStartKey(), than.GetStartKey()) < 0
 }
 
 // StartKey returns the start key of the item.
diff --git a/server/core/region_tree_test.go b/server/core/region_tree_test.go
index 3237a5daf..f50073f60 100644
--- a/server/core/region_tree_test.go
+++ b/server/core/region_tree_test.go
@@ -466,7 +466,7 @@ func BenchmarkRegionTreeSequentialLookUpRegion(b *testing.B) {
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
 		index := i % MaxCount
-		data.tree.find(data.items[index])
+		data.tree.find(&regionItem{RegionInfo: data.items[index]})
 	}
 }
 
@@ -475,7 +475,7 @@ func BenchmarkRegionTreeRandomLookUpRegion(b *testing.B) {
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
 		index := i % MaxCount
-		data.tree.find(data.items[index])
+		data.tree.find(&regionItem{RegionInfo: data.items[index]})
 	}
 }