# Interval Tree

Interval Tree(区段树)在内存管理中有用到，比如rmap和vma中。

一直觉得有点神秘，今天来看一下。

## 是附带属性的红黑树

本质上区段树是一个红黑树，在红黑树的基础上增加了两个信息：

* leftmost: 保存了整个树中最左叶子
* subtree: 每个节点增加当前子树内区间最大值

## 优势

和红黑树相比，区段树的优势在与查找某区间内有较差的节点时，可以借助新增的这两个信息加速查找。

具体参考区段树提供的api：

* interval\_tree\_iter\_first()
* interval\_tree\_iter\_next()

## 测试代码

内核中有相关的测试代码，lib/interval\_tree\_test.c。这样可以看出简单的使用方法。