[数据结构与算法]红黑树在Linux内核中的应用

数据存储的方式

存储数据的方式，常见的会使用两种，一种是链式结构，另一种是树型结构。

• 链式结构
  链表，队列，栈
• 二叉树
  红黑树，B树，B+树

红黑树的概念

红黑树是非常重要的一个概念，对于技术的理解有必要非常精准地表达出来，二不是非常模糊地用可能这样的词汇。普遍的工程师，能够使用技术词汇，但是不能精准地使用它们。

红黑树的性能

• 每个节点是红色的或者黑色的
• 根节点是黑色的
• 每个叶子节点是黑色的
• 如果一个节点是红色的，那么它的两个儿子都是黑色的
• 对于每一个节点，到达所有的叶子节点，有相同的黑色节点

如果要插入一个新节点的时候，为了不破坏黑高，最好插入红色节点。
在插入红色节点的时候，如果父节点是红色的，需要调整，因为破坏了红黑树的定义4.
如何去证明红黑树呢？红黑树如何做到线程安全呢？

红黑树的用途

1. 以key value的方式进行索引
2. 利用其排序的性质，中序遍历是有序的

在内核里面使用红黑树的场景

• 进程调度
  一个进程对应一个task_struct
  每次使用fork()的时候，一个进程会变成两个，复制了一个struct_struct结构体（写时复制），因为新的结构不一定适用，所以边执行边修改。所有的进程，都是由父进程创建出来。
  默认调度基于CFS，即完全公平调度算法，在调度实体中有个vruntime，会根据这个vruntime进行调度

• 内存管理
  每个进程都有自己的mm_struct，使得每个进程都有自己独立的虚拟的地址空间

  struct mm_struct {
  struct vm_area_struct * mmap;    //指向虚拟区间(VMA)的链表
  struct rb_root mm_rb;            //指向线性区对象红黑树的根
  struct vm_area_struct * mmap_cache;     //指向最近找到的虚拟区间
  unsigned long(*get_unmapped_area) (struct file *filp,
  unsigned long addr, unsigned long len,
  unsigned long pgoff, unsigned long flags);//在进程地址空间中搜索有效线性地址区
  .....
  }
  

  对于一块内存，有这几种方法来获取，start address和end address，start address和长度

• xxxx

当前职场工程师深思

很多技术名词看起来都懂，但是细问的话，发现并非真的理解它们，这是为什么呢？在大学主要以准备考试为主，走入职场后又主要以写业务代码为主，对于基础知识搁浅了。
大部分的工程师所学习的知识主要源自道听途说，比如一些博客，比如一些新闻，而非来自真正的论文和源代码。
国外企业面试，更加注重一个人的创造能力，而非那些所谓的业务（比如MQSQL使用，redis等等）。
作为程序员，一定要将自己的基础知识给补充起来，培育自己的创造力，培育自己的那种从0到1的能力。