《linux内核设计与实现》--2、内核数据结构

• 内核数据结构
  • 链表
    • 是一种存放和操作可变数量元素（节点）的数据结构。
    • 单向链表
      • 包含一个有效数据和一个指向下一个节点的指针。链表尾元素指针指向NULL。只能正向遍历。
      • 
    • 双向链表
      • 除了单向链表特征外，还包含了指向上一个节点的指针。可以同时向前或向后相互连接。可以反向遍历。
        •  
    • 环形链表
      • 除了含有链表的特征外，尾元素指针不再指向NULL，而是指向首元素；首尾相连。
      • 环形链表也存在，环形单向链表，环形双向链表（Linux用的这个）。
      • 
      •  
    • 链表操作的时间复杂度为O(1)，包含：增加、删除、移动等；遍历链表的时间复杂度为O(n)。
    • Linux内核方式与众不同，它不是讲数据结构塞入链表，而是将链表节点塞入数据结构！
  • 队列FIFO
    • 生产者、消费者。生产者创造数据，消费者处理数据。先进先出。
    • 
    • enqueue（入队列）：操作拷贝数据到队列到入口偏移位置。入口偏移位置随着加上推入到元素数目。
    • dequeuq（出队列）：操作从队列中出口偏移处拷贝数据。出口偏移随着减去摘取到元素数目。
      • 出口偏移量：下一次出队列时都位置；出口偏移量总是小于等于入口偏移量。
      • 入口偏移量：下一个入队列时都位置；
  • 映射
    • 一个映射也称为关联数组，是一个由唯一键组成到集合，每个键对应一个特定到值。这种键到值到关联关系称为映射。
  • 二叉树
    • 树是一个无环、连接的有向图，其中任何一个顶点具有0个或者多个出边以及0个或者1个入边。
    • 树的高度是指树中的处于最底层节点的深度。
    • 二叉树是每个节点最多只有两个出边的树，即每个节点具有0个、1个或者2个子节点。
    • 二叉搜索树（BST）是一个节点有序的二叉树：
      • 根的左分支节点的值都小于根节点值。
      • 右分支节点值都大于根节点值。
      • 所有的子树都是二叉搜索树。
      • 
      • 平衡二叉搜索树
        • 所有叶子节点深度差不超过1的二叉搜索树。
        • 其操作都试图维持（半）平衡的二叉搜索树。
        • 
  • 红黑树
    • 自平衡二叉树的一种，具有着色属性，或红色或黑色，维持半平衡结构：
      • 所有的节点要么着红色，要么着黑色。
      • 叶子节点都是黑色。
      • 叶子节点不包含数据。
      • 所有非叶子节点都有两个子节点。
      • 如果一个节点是红色，则它的子节点都是黑色。
      • 在一个节点到其叶子节点的路径中，如果总是包含同样数目的黑色节点，则该路径相比其他路径是最短的。
    • 最短路径必然是只包含黑色节点的路径。从根节点到叶子节点的最长路径不会超过最短路径的两倍。
    • linux中的红黑树称为：rbtree。
• 数据结构的选择：
  • 对数据集合的主要操作是遍历，则使用链表。
  • 当性能并非首要考虑因素、或需要存储的数据项较少、或需要和内核中的其他使用链表的代码交互时，应优先选择链表。
  • 需要存储一个大小不明的数据集合，链表可能更适合，因为可以动态添加任何数量的数据项。
  • 如代码符合：生产者/消费者模式，则使用队列；队列会是的添加、删除项的工作简单有效。
  • 如需要映射一个UID到一个对象，则使用映射。Linux的映射接口是针对UID到指针的映射，不适合其他场景，如需处理发给用户空间的描述符，可以考虑用映射。
  • 如需存储大量数据，且检索迅速，则红黑树最好；红黑树可确保搜索时间复杂度是对数关系，同时也保证按序遍历时间复杂度是线性关系。
  • 如无需多次执行时间紧迫的查找操作，则红黑树可能不是最好的选择；此时可选用链表。
  • 算法复杂度
    • 算法的复杂度量化表示，最常用的技术是研究算法的渐近行为。
    • 渐近行为：指当算法输入变得非常大或接近于无限大时算法的行为。
    • 算法：是一系列的指令，可能有一个或多个输入，最后产生一个结果或输出。
    • 大O符号
      • 一种很有用的渐近表示法就是上限（一个函数，其值从一个起始点之后总是超过我们所研究的函数的值），也就是上限增长等于或快于我们研究的函数；大O符号用来描述这种增长率。
      • 函数f(x)可以写作O(g(x))，读：f是g的大O，数学定义如下：
      • 
    • 大θ符号
    • 最小上限，一个抽象出具有上限和下限的函数。

    • 

    • 时间复杂度
      • 常见的时间复杂度：

        

        ​​​​​​​
      • 不能仅仅依靠算法的复杂度（大O符号）来判断哪种算法在实际试用中性能更高；指定的O(g(x))有一个恒量c和g(x)相乘；所以O(1)固定时长，可能比复杂度O(n)但输入很少的算法更耗时。
      • 因此在比较算法性能时，还需要考虑输入规模。避免盲目优化算法。

​​​​​​​