思维导图
相关数据结构
vm_area_struct
vm_area_struct可以描述一个VMA区域的起始地址和大小，区域的属性，由vm_flags表示。
红黑树
红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为“对称二叉B树”，它现代的名字源于利奥尼达斯·J·吉巴斯和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在O(logn)(大O符号)时间内完成查找、插入和删除，这里的n是树中元素的数目。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点必须有两个黑色的子节点。（或者说从每个叶子到根的所有路径上不能有两个连续的红色节点。）（或者说不存在两个相邻的红色节点，相邻指两个节点是父子关系。）（或者说红色节点的父节点和子节点均是黑色的。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
红黑树本质上还是一个二叉搜索树（左边的值都比右边小），但是它能借助其额外的特性保证从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。
maple_tree
Maple Tree是一种基于 RCU 的支持区域的 B 树（RCU-safe range based B-tree），旨在高效地使用现代处理器高速缓存。内核中有很多地方基于不重叠范围的树将是有益的，。如果将 rbtree 与其他数据一起使用用于提高性能的结构或用于跟踪的区间树不重叠的范围，那么Maple Tree非常适合。
该树的非叶节点的分支因子为 10，叶节点的分支因子为 16节点。随着分支因子的增加，它明显变短。与 rbtree 相比，它的cache miss更少。删除双链也减少了cache miss。
它覆盖的第一个用户是 vm_area_struct，其中三个数据结构被替换：增强的rbtree、vma cache和 mm_struct 中的 VMA linked list。长期目标是减少或消除 mmap_lock 争用。
🕊🕊🕊
整体结构概述
红黑树版本
红黑树的作用是快速查找与插入：利用其快速查找的特性可以很快判断一段地址是否被分配过；如果新分配了一片虚拟地址也可以很快地插入到红黑树中。
感觉链表存在的意义是方便遍历（就是不是查找而是遍历的时候）❓😢
maple_tree版本
🕊🕊🕊
参考
https://www.cnblogs.com/banshanjushi/p/17991727
https://zh.wikipedia.org/zh-cn/%E7%BA%A2%E9%BB%91%E6%A0%91
https://my.oschina.net/emacs_8798868/blog/17289911
https://blog.csdn.net/wwwlyj123321/article/details/128355056
