区间树：反向映射的前置数据结构
这篇只讲一个前置数据结构：区间树。
先不展开anon_vma、anon_vma_chain、vma、folio这些内核结构。真正讲匿名页反向映射时，再把这些结构套进来。
先给一个简短定义：
区间树可以理解成一棵被增强过的有序平衡树。原本平衡树的节点通常保存一个具体的 key；区间树把节点保存的内容换成一个区间[start,end]，排序和查找时主要比较区间的start端点。然后，它在每个节点上额外维护一个maxEnd字段，表示这棵子树里所有区间最大的end。当树上的区间插入、删除或变化时，底层平衡树要继续维护平衡，区间树这一层还要同步维护受影响节点的maxEnd。
现在只抓住一个核心问题：
给定一个查询点或查询区间， 在很多已经保存好的区间里， 快速找出所有和它重叠的区间。
两个闭区间：
A = [a_start, a_end] B = [b_start, b_end]
相交条件是：
a_start <= b_end && b_start <= a_end
如果查询是一个点q = 100，可以把它看成区间[100,100]。所以点查询和区间查询可以统一起来。
一、最小问题：找所有重叠区间
先有一批区间：
[ 80, 120] [100, 140] [300, 360] [ 96, 111]
现在查询：
Q = [100, 101]
逐个判断：
[ 80, 120] 命中 [100, 140] 命中 [300, 360] 不命中 [ 96, 111] 命中
最直接的实现是数组扫描：
for each interval: if interval.start <= Q.end && Q.start <= interval.end: hit
复杂度是：
O(n)
区间数量少时，这没问题。区间很多、查询频繁、还要插入删除时，就需要索引。
二、先把区间放进普通搜索树
一个自然想法是：按区间起点start建一棵搜索树。
key = interval.start
每个节点先只保存自己的区间和左右孩子：
node ├─ interval = [start, end] ├─ left 所有 start 更小的区间 └─ right 所有 start 更大的区间
把这些区间插进去：
[ 80, 120] [100, 140] [300, 360] [ 96, 111]
一棵可能的树是：
[80,120] \ [100,140] / \ [96,111] [300,360]
这时候树已经形成了。它是一棵按start排序的普通区间搜索树，但还不是完整的 interval tree。
这棵树能帮我们做一部分剪枝。比如查询[100,101]时，节点[300,360]的start = 300已经大于查询右端101，它和它右边那些start更大的节点都不可能命中。
但只按start排序还不够。
三、只按 start 排序为什么不够
看一棵按start排序的树：
[100,140] / \ [80,120] [300,360] / [1,1000000]
查询：
Q = [500, 501]
站在根节点[100,140]看，左子树里的区间起点都更小：
[80,120].start = 80 [1,1000000].start = 1
但是左子树不能直接跳过。因为：
[80,120] 80 <= 501 && 500 <= 120 不命中 [1,1000000] 1 <= 501 && 500 <= 1000000 命中
也就是说，只知道左子树的start都更小，不能说明左子树里所有区间都已经结束了。
普通按start排序的树缺少一个信息：
这棵子树里，最大的 end 是多少？
如果不知道这个信息，就无法判断一整棵子树能不能被跳过。最坏情况下，还是会退化成大量扫描。
到这里，再把层次关系分清楚就比较自然了：
底层树： 负责维护有序结构，比如红黑树、AVL 树、B-tree。 区间树这一层： 把每个树节点里的数据换成一个区间 [start,end]； 用 start 作为主要排序 key； start 相同时再用 end 或节点身份做 tie-break； 再额外维护“这棵子树里最大的 end”这个摘要字段； 查询时用这个摘要字段跳过不可能命中的整棵子树。
所以 interval tree 不是说发明了一套新的平衡规则。它更像是：
ordered balanced tree + interval stored in each node + subtree summary field + overlap query algorithm
下一节就给这个摘要字段起一个名字：maxEnd。
四、加增强字段：maxEnd
区间树的关键就是在普通搜索树节点上加一个增强字段：
maxEnd = 以当前节点为根的整棵子树里，所有区间最大的 end
节点变成：
node ├─ interval = [start, end] ├─ left ├─ right └─ maxEnd
要注意：
x.maxEnd 表示以 x 为根的整棵子树里的最大 end。 node.left.maxEnd 表示 node 的左子树里的最大 end。 node.right.maxEnd 表示 node 的右子树里的最大 end。
maxEnd的作用是判断某棵子树有没有必要进去查。
比如查询：
Q = [100, 101]
有这样一棵树：
[100,140], maxEnd=360 / \ [40,60], maxEnd=90 [300,360], maxEnd=360 / \ [10,20], maxEnd=20 [70,90], maxEnd=90
站在根节点[100,140]，看左孩子：
left.maxEnd = 90 Q.start = 100
因为：
90 < 100
所以左子树里所有区间都在Q.start之前结束，不可能和[100,101]相交。整棵左子树可以跳过：
[40,60] [10,20] [70,90]
当前节点[100,140]和查询区间相交，命中。
右子树[300,360]的start > Q.end，不命中。
这就是maxEnd的价值：它不是判断某个单独节点，而是判断一整棵子树有没有可能包含答案。
五、查询逻辑
查询一棵区间树时，可以按下面的逻辑走：
query(node, Q): if node == null: return if node.left != null && node.left.maxEnd >= Q.start: query(node.left, Q) if node.interval 和 Q 相交: 记录 node.interval if node.interval.start <= Q.end: query(node.right, Q)
左子树判断：
node.left.maxEnd >= Q.start
含义是：
左子树里至少可能有一个区间的 end 到达 Q.start； 所以左子树可能有命中，需要进去查。
如果：
node.left.maxEnd < Q.start
说明：
左子树里所有区间都在 Q.start 之前结束； 整棵左子树都不可能命中。
右子树判断：
node.interval.start <= Q.end
因为右子树里的start都大于等于当前节点的start。如果当前节点的start已经大于Q.end，右子树只会更靠右，也不可能命中。
如果底层树保持平衡，查找所有重叠区间可以理解成：
O(log n + k) n = 树里区间数量 k = 本次命中的区间数量
这里的k不能省。如果确实有很多区间都和查询区间重叠，算法至少要把这些结果返回出来。
六、动态更新：插入、删除和区间变化
如果区间集合永远不变，那建好树之后只查就行。
但真实系统里的区间经常变化：
新增一个区间； 删除一个区间； 一个旧区间缩小、扩大或者被拆成多个区间。
所以区间树还要解决第二个问题：
树变了以后，maxEnd 怎么快速维护？
插入一个新区间时，过程和普通搜索树插入很像：
1. 按 start 找到它应该插入的位置。 2. 插入新节点。 3. 从插入路径往上回溯，重新计算沿途节点的 maxEnd。
maxEnd的重新计算只依赖三个值：
node.maxEnd = max(node.interval.end, node.left.maxEnd, node.right.maxEnd)
所以不需要重扫整棵树，只要更新被插入路径影响到的祖先节点。
删除一个区间也是类似的：
1. 按 start/end 找到要删除的节点。 2. 按普通搜索树或红黑树删除节点。 3. 从结构发生变化的位置往上，重新计算 maxEnd。
如果底层树是红黑树或 AVL 树，插入和删除过程中还可能发生旋转。旋转属于底层平衡树的维护动作；interval tree 这一层要做的是：旋转完成后，把被旋转影响到的几个节点重新计算maxEnd，再继续向上维护即可。
这篇 demo 选择 AVL 树做底层平衡树，所以代码里会看到一个height字段。它的作用不是查重叠区间，而是让 AVL 树判断自己有没有失衡：
balance = height(left) - height(right) balance > 1 左子树太高，需要旋转 balance < -1 右子树太高，需要旋转
如果不维护height，每次判断一个节点是否失衡都要重新计算左右子树高度，插入删除会多出很多重复扫描。维护height后，判断平衡因子就是O(1)。
