《Operating System Concepts(操作系统概念)》核心笔记

一、操作系统结构

1.人机交互

方式：GUI（图形用户界面）与命令解释程序。后者又称作外壳(shell)。

2.系统调用

2.1分类：Windows API(Windows系统)、POSIX API(POSIX系统)、java API(java虚拟机)。
2.2使用：程序员一般不直接使用系统调用，而是使用API。如C语言的libc。因为API使用方便，系统调用更注重细节。API函数库帮助我们调用系统调用。
2.3实现：以C语言的open()API为例，编译得到可执行文件，并运行。此时动态链接器会将glibc链接到该进程虚拟地址空间。运行到read代码段时glibc会向内核的系统调用接口传递系统调用号这一数字，并通过内核指定的寄存器传递参数。
2.4分类：进程控制、文件管理、设备管理、信息维护、通信、保护。

3.微内核

3.1功能：只提供调度、内存管理和进程通信。
3.2特点（对比宏内核）：微内核非核心的内核功能由用户态的二进制程序实现。宏内核所有内核功能都由.ko内核文件实现。
3.3代表操作系统：Windows NT，QNX，Tru64 Unix。

4.混合系统

4.1功能：内核提供核心服务，如调度与内存管理，其他的功能由别的.ko内核模块实现，需要时动态加载，但不像微内核，这些内核模块像函数一样直接相互调用，因为共享地址空间。

5.系统启动

5.1传统Linux系统启动方式（BIOS+MBR）：​​BIOS​​ 从磁盘LBA 0（0号扇区）加载512字节MBR（文件为boot.img）到内存0x7C00并执行。MBR引导代码​​（前446字节）加载GRUB第二阶段（core.img）到内存0x8000，跳转执行。core.img解析grub.cfg，若双系统则显示grub窗口，加载用户选择的Linux内核或Windows Boot Manager到内存。————链式加载
5.2现代Linux系统启动方式（UEFI+GPT）：UEFI不读取MBR​​，而是从 ​​ESP分区（EFI System Partition）​​ 加载 .efi 文件（如 grubx64.efi）。.efi 文件直接解析grub.cfg文件。
5.3Windows系统启动：传统方式大差不差，都是链式加载。现代方式下Windows会在ESP分区建立Microsoft文件夹存放其efi文件。若为双系统，则UEFI会根据配置选择加载Windows的efi文件或是Linux的efi文件。

二、任务调度

注：不再区分进程、（内核）线程、任务。

1.调度算法

1.1调度器分类：
短期调度程序/CPU调度程序——选择进程（任务）上CPU。
长期调度程序/作业调度程序——选择进程上内存，控制内存中的进程数量。（Windows、Unix没有）
1.2调度算法评价指标：
吞吐量：单位时间完成任务的数量。
等待时间：进程在就绪队列等待的时间。多用平均值。
响应时间：用于交互式系统，提交请求到产生首次相应的时间。
1.3调度算法分类：
a.先到先服务（First-Come First-Served, FCFS)。
b.优先级调度：最短作业优先（Shortest-Job-First, SJF)/最短下次CPU执行（平均等待时间最少，最优）、抢占式最短作业优先（最短剩余时间优先）：可能导致优先级低的进程饥饿，但可通过老化避免。
c.轮转调度：专门为分时系统设计。时间片过小会导致更频繁的上下文切换的时间浪费。时间片过大就不再是分时系统而是FCFS系统了。
d.多级队列调度：将就绪队列分为多个单独队列，每个队列有自己的调度算法。划分方法可以是前台与后台划分。队列与队列之间通常采用固定优先级抢占调度，如前台队列对后台队列绝对优先。进程无法中途更换队列。
c.多级反馈队列调度：同多级队列调度，但进程随时间会更换队列，这允许等待过长的进程被移到高优先级队列，防止饥饿。

2.线程竞争范围

1.分类：用户级线程通常与同一进程的其他线程竞争谁能上进程被调度执行，称为进程范围竞争(Process-Contention Scope, PCS)，内核级线程与整个系统的内核级线程竞争上CPU，称为系统竞争范围(System-Contention Scope, SCS)，所有系统都有SCS，采用一对一模型的系统，如Linux、Windows，只有SCS调度。

3.常见操作系统调度算法

a.Linux——完全公平调度程序(Completely Fair Scheduler, CFS)：进程的优先级为0~139，其中分为两个范围。0~99用于实时任务，100~139用于普通任务。实时任务对于普通任务可抢占。实时任务之间根据优先级，低的可抢占高的。普通任务根据nice值映射到100~139的优先级。普通任务的优先级仅仅代表CPU时间分配的长短，不能抢占。
b.Windows——优先级多级反馈队列抢占调度算法：采用32级优先级，1~15级为可变类，16~31级为实时类，一个可变优先级的线程的每用完一个时间片便降低一个优先级等级但最终不低于优先级基值（可设置），当其等待的IO结束时其优先级会提升。

三、同步

C++ STL中的栈与队列：核心原理与实战应用指南

在C++标准模板库（STL）中，stack（栈）和queue（队列）是两个重要的容器适配器，它们通过封装底层容器（默认使用deque）实现了特定的数据操作逻辑。本文将深入探讨它们的设计原理、常用操作及典型应用场景，帮助开发者快速掌握其核心用法。

一、栈（stack）：后进先出的数据管理
核心特性与初始化

栈遵循后进先出（LIFO）原则，仅允许在栈顶进行插入和删除操作。其底层通常基于deque或list容器实现。

include <stack>

std::stack<int> s;  // 默认基于deque的整型栈

常用操作及示例

方法         功能描述 示例代码

push(x) 将元素x压入栈顶 s.push(10);
pop() 移除栈顶元素（不返回值） s.pop();
top() 返回栈顶元素的引用（需非空检查） int val = s.top();
empty() 判断栈是否为空（返回布尔值） if (s.empty()) {...}
size() 返回栈中元素数量 int cnt = s.size();

操作示例：遍历栈并输出所有元素

std::stack<int> s;
s.push(1); s.push(2); s.push(3);
while (!s.empty()) {
    std::cout << s.top() << " ";  // 输出：3 2 1
    s.pop();

典型应用场景

括号匹配：通过栈结构检测表达式中的括号嵌套是否正确

深度优先搜索（DFS）：递归算法中隐式使用栈管理访问路径

撤销操作：文本编辑器中按顺序记录操作步骤

二、队列（queue）：先进先出的任务调度
核心特性与初始化

队列遵循先进先出（FIFO）原则，元素在队尾插入，队首删除。底层同样基于deque或list实现。

include <queue>

std::queue<std::string> q;  // 字符串队列

常用操作及示例

方法         功能描述 示例代码

push(x) 将元素x插入队尾 q.push("task1");
pop() 移除队首元素（不返回值） q.pop();
front() 返回队首元素的引用（需非空检查） auto task = q.front();
back() 返回队尾元素的引用 auto last = q.back();
empty() 判断队列是否空 if (q.empty()) {...}
size() 返回队列元素数量 int len = q.size();

操作示例：处理任务队列

std::queue<int> q;
q.push(10); q.push(20); q.push(30);
while (!q.empty()) {
    std::cout << q.front() << " ";  // 输出：10 20 30
    q.pop();

典型应用场景

广度优先搜索（BFS）：按层次遍历树或图结构

消息队列：异步处理系统中的任务缓冲

打印任务调度：保证文档按提交顺序打印

三、进阶扩展：优先队列（priority_queue）
优先队列是队列的变种，元素按优先级排序（默认最大堆）。常用于任务调度系统：
include

// 小顶堆示例
std::priority_queue<int, std::vector, std::greater> pq;
pq.push(3); pq.push(1); pq.push(4);
pq.top(); // 返回1（当前最小元素）

一、插入排序

1.直接插入排序与折半插入排序。

　　1.1步骤：
　　　(1)对于第i个元素，先用临时变量保存之，然后在1 ~ i-1的有序序列中找到其该插入的位置k。
　　　(2)将k到i-1的所有元素后移一位，导致k被腾出。
　　　(3)将临时变量保存的i号元素赋值到k位置。
　　*对于折半插入排序，因为i前必有序，找插入位置可使用折半查找。注意mid与临时变量相等时（即序列有重复元素），让low = mid + 1而非直接结束，最后将low ~ i-1或high+1 ~ i-1的元素往后移动一位腾出位置供插入。k=low。这样做是为了保证稳定性。考虑abcccdec，最后一个c为待插入前面的元素，mid=4与临时变量匹配就认为找到了k的话，在5的位置还有一个c就会被移动，就不稳定。
　　*对于直接插入排序，步骤(1)的找位置与步骤(2)同时进行。
　　*时间复杂度为O(n^2)。空间复杂度为O(1)。稳定。

2.希尔排序/缩小增量排序

　　2.1思想：
　　　以逐渐减小为1的增量（步长）划分子表，一个增量d可以把原序列化为d个子表，对每个子表插入排序即可。增量为1就是直接插入排序了。
　　*时间复杂度不明。空间复杂度为O(1)。不稳定。

二、交换排序

1.冒泡排序

　　*对于求冒泡的趟数的，把每一趟结束的序列写出来不要偷懒。最后千万别忘了得到一个排完序的序列之后实际上程序还要再跑一趟从而发现没有进行任何交换才会结束。
　　*时间复杂度为O(n^2)。空间复杂度为O(1)。稳定。

2.快速排序

　　*思想：移走首元素留下空位，比首元素（枢轴pivot）小的移到前面空位从而在后面产生空位，大的移到后面空位从而在前面产生空位，两者交替，最终空的就是存放首元素的位置。
　　*画二叉排序树的心算方法：把序列写出来，把首元素（枢轴pivot）写到序列下面，序列与其下的pivot充当一个结点。左手手指为low指针，右手笔为high指针，分别指向序列首尾。先low不动，high从当前位置的前一位开始判断是否比pivot小，不是则写入到该结点右分支的最左，high往左移动并继续判断，直到找到并写入到该结点左分支的最右或high与low相等则表明该结点成功生成子结点了。若结束原因非后者，则此次是保持high不变，low从其后一位开始移动直到low指向的大于pivot从而写入到high的位置或low与high相等。两者如此交替重复几轮终会导致low=high。此时两个子结点就生成完毕。然后对两个子结点的序列进行同样的操作。（详见王道p351第10题）
　　*时间复杂度：最好时树高logn，树的每一层low与high都对整个序列一个个的遍历，为n。故最好时间复杂度O(nlogn)。最坏树是单支树，O(n^2)。快速排序发生最好的情况的概率更大，故平均时间复杂度O(nlogn)。
　　*空间复杂度：即同时处于栈段的函数栈的个数，即树的树高，因此最好O(logn)最坏O(n)，平均O(logn)。
　　*定下一个序列的枢轴最终所在的位置需要比较的次数就是该序列长度-1。因为所有的比较无非就是枢轴元素与其他所有元素的比较。

三、选择排序

1.简单选择排序

　　*思想：每次从无序序列中选出最大/最小的元素交换到有序序列前/后一位。

2.堆排序

　　*堆即顺序存储的，根与其两个孩子有大小关系的完全二叉树。若堆有n个元素，则非叶结点的数量为⌊n/2⌋个。
　　*堆分为大根堆与小根堆。
　　步骤：
　　a.先将序列建堆。方法是序列前⌊n/2⌋个元素调用HeadAdjust函数。该函数针对传入其的根结点，暂存根结点并产生k与i双指针，其中k永远是i的双亲。在一个i每次乘2（指向其左孩子）的循环中，先比较左右孩子孰大孰小以确定i是否+1成为k的右孩子，在比较i与k孰大孰小决定是否让i移动到k的位置上，若无需移动则表明当前k结点为根的树符合堆的定义了，否则接下来k=i调整其子树成为堆。
　　b.建立n-1次的循环。这里与选择排序一致，因为堆顶一定是最大/小的元素，省去了选择排序遍历的麻烦。但每次将堆顶元素交换到后面都要调用HeadAdjust函数调整前面。
　　*建堆时间复杂度O(n)，堆排序时间复杂度O(nlogn)，总体O(nlogn)，空间复杂度O(1)。不稳定。
　　*堆的插入操作：新结点放序列末尾，然后向上调整。时间复杂度O(logn)。
　　*堆的删除操作：删除结点，以序列末尾元素代替。然后向下调整。时间复杂度O(logn)。
　　*题目若要求堆排序、堆插入或堆删除的比较次数，对每个结点，先比较其两个子结点的大小，选出有资格与该结点比较的子结点与该结点比较。子结点若不为叶结点则继续往下记录比较次数。
　　*题目若要求堆排序、堆插入或堆删除的交换次数，对每个结点，若其子结点移动到该结点的位置就算“交换”，即使实际代码中子结点并没有被该结点赋值。

四、归并排序

　　1.思想（以排成从小到大的序列为例）：
　　*全局建立一个辅助数组B，长度与序列长度相同。（因为首位弃用故长度为元素个数+1）
　　*函数Merge:传入待排序数组A，以及low,high,mid。左半部分数组为A[low~mid]，右半部分数组为A[mid+1~high]，两个子数组都有序。将所有这些元素通通移动到B中同下标的位置。然后设置三指针i,j,k。i为B中左半部分数组的移动索引，j为B中右半部分数组的移动索引，k为A的移动索引。循环比较B[i]与B[j]，谁小谁移到B[k]（相等则先把左子数列中的移到A保证稳定性），A[i]移走i++，A[j]移走j++，k不管谁移走都要加1。最终因为i与j的任何一个出界退出循环。最后再将没有移动完的B的子数组移动到A剩余位置。
　　*函数MergeSort:利用递归，递归结束条件是传入该层递归函数的low与high相等，否则产生变量mid=(low+high)/2，以low到mid调用他自己，再以mid+1到high调用他自己。最后调用Merge将low到high中的序列排有序。

2.排序趟数取决于树高，O(logn)，每趟O(n)，时间复杂度O(nlogn)，空间复杂度O(n)，稳定。

五、基数排序

　　1.思想：从关键字本身的信息出发，设关键字为r进制，位数为d位，个数为n个。设置r个队列，将最低位，放进相应队列（分配），再将各个队列的关键字保持先后顺序的拿出来存进链表（收集），再到下一位直至最高位。从高位出发到低位亦可行。
　　2.共d趟，每趟分配O(n)，收集O(r)，时间复杂度O(d(n+r))，空间复杂度O(r)。

一、线性表查找算法

1.顺序查找

　　•顺序查找无视待查表的有序与否。

2.折半查找

　　•折半查找只能用于顺序存储的线性表。
　　•表的各个元素在判定树中所在的树高就是其比较次数。对于失败情况所在的叶节点，其比较次数为其所在树高-1。判定树高度计算式与完全二叉树一致——里上外下。
　　•求ASL：画判定树，然后利用ASL定义计算。
　　•画判定树：别像个乌龟一样脑海中模拟一遍折半查找才画完树，用简便方法——逐个往树上添加结点，若是mid = (l + r)/2，要求使判定树中的每个子树的左子树结点数=右子树结点数，或左子树结点数+1=右子树结点数（因为当l与r之间有奇数个表项，mid算出来就是中间那个，其左右子树结点相等；当l与r之间有偶数个表项，mid的左子树就会比右子树少一个结点）。最后画完时，为树中原有的每个空链域添加一个叶结点表示失败情况。

3.分块查找/索引顺序查找

　　•求ASL：
　　　-通过定义求：每一个表项的查找次数 = 其所在块在索引表的位置 + 其在块中的位置。通过定义求和所有块的所有表项即可（很麻烦）。
　　　-简便方法：ASL = 索引表的ASL + 单个块的ASL。索引表的ASL和单个块的ASL由定义求出。

4.散列表（哈希表）

　　•求ASL：
　　•开放寻址解决冲突的散列表的相邻地址不一定存储同义词，是交错排列的。
　　•链地址法（拉链法）不可能造成聚集现象。（聚集——多个不同初地址关键字抢夺同一个地址进行插入）
　　•散列表的ASL或时间复杂度与装填因子直接相关，与不直接依赖于关键字数或散列表容量。

二、树形查找

1.二叉排序树（BST, Binary Search Tree）

　　1.1 查找：
　　　　——循环实现：使用游离指针T指向根结点，开始循环，当游离指针指向的结点为待找结点（找到）或游离指针指向NULL（没有该结点）时退出循环，否则让T指向该结点的左右孩子结点（待查找值小于T时让T指向T的左孩子，当待查找值大于T时让T指向T的右孩子）。
　　　　——递归实现：递归函数是递归结束函数的条件仍然是找到或当前传入的结点已经为NULL，此时返回T。递归函数是递归中间函数的条件相反，即传入的结点不为空，但又不与待找结点相同，那就分小于与大于，待找结点小于当前传入函数的结点时，返回递归调用左子树的结果，反之递归调用右子树的结果。
　　1.2 插入（递归实现）：递归函数是递归结束函数的条件是找到相同的或当前传入的结点为NULL，相同则返回错误，为NULL则修改该结点为malloc新建结点的返回值。递归函数是递归中间函数的条件相反，即传入的结点不为空，那就分小于，大于与等于，待找结点小于当前传入函数的结点时，返回递归调用左子树的结果，反之则递归调用右子树的结果。
　　1.3 构造：从头遍历关键字序列，对每一个序列调用插入操作。
　　1.4 删除：查找该结点在树中的位置。
　　　　——若该结点是叶节点，则直接删除。
　　　　——若该结点只有左子树或只有右子树，则直接让其子树的根节点代替它。
　　　　——若该结点既有左子树又有右子树，则需要让其直接前驱或直接后继复制给它。找直接前驱：中序遍历其左子树，最后遍历到的即其直接前驱。找直接后继：中序遍历其右子树，最先遍历到的即其直接后继。然后删除其直接前驱或直接后继的所处的结点（该结点肯定是叶节点或只有左子树/右子树）。
　　•中序遍历即可得到一个二叉排序树的有序序列。同一个序列的所有二叉排序树中序序列相同，且这些二叉树的中序序列就是该序列。
　　•卡特兰数 = n个结点构造的不同二叉排序树的个数 = 中序确定，不同先序序列的个数。计算式在王道书p301。

2.平衡二叉树（AVL树，取名为开发者名字首字母）

　　•平衡二叉树用于二叉排序树，使得查找时间为O(logn)，更快。
　　2.1 插入与删除：
　　　（1）直接插入，删除。
　　　（2）从插入/删除的点向上找最小不平衡树的根结点r。
　　　（3）找到该根结点r的高度最高的儿子结点x，结点x高度最高的儿子结点y。
　　　（4）分以下四种情况：
　　　　a.x,y都是左孩子——r相对x右（下）旋
　　　　b.x,y都是右孩子——r相对x左（下）旋
　　　　c.x左y右——x相对y左（下）旋，然后r相对y右（下）旋
　　　　a.x右y左——x相对y右（下）旋，然后r相对y左（下）旋
　　•ab情况是x成为最终根结点，cd情况是y成为最终根结点。
　　　（5）若是删除操作，则需要继续向上找有没有不平衡的结点。
　　•因为插入操作的插入操作本身及其后的四种平衡处理最终不会影响最小不平衡树的树高，而删除操作的删除操作本身及其后的四种平衡处理可能会使最小不平衡树的树高 - 1导致其祖先结点不平衡。
　　2.2 结点数分析
　　•平衡二叉树达到树高h的最少结点数：n(h) = n(h-2) + n(h-1) + 1，即树高为h所需的最少结点为将树高为h-1与树高为h-2的结点用一个根结点相连即可。
　　•平衡二叉树不超过树高h的最多结点数：满二叉树。
　　•平衡二叉树给定结点数的树高最低为里上外下，但可以更高。不同于完全二叉树给定结点数它就是一定是里上外下的树高。但是若从空树开始，插入序列是升序的，则产生的平衡二叉树的高度就是结点数对应的完全二叉树高度。
　　•平衡二叉树的一个结点的两个孩子平衡因子都为0，该结点平衡因子不一定为0。

3.红黑树（RBT）

　　3.1 原则：左根右，不红红，根叶黑，黑路同。
　　3.2 树形/时间复杂度分析：
　　结点黑高——结点到任意叶节点的路径上的黑结点数（不计该结点）。
　　树的黑高——根结点到任意叶节点的路径上的黑结点数（不计根结点）。
　　•树高（不算叶节点）最少为树黑高（全黑），最多为树黑高的两倍（黑红相间）——这是红黑树较平衡二叉树放宽松的地方。
　　•一个红黑树的黑高为bh，则该二叉树结点最少的情况为该树是高度为bh的满二叉树且全为黑结点，最多为该满二叉树两两黑结点之间添加红结点成为高度为2bh的满二叉树。
　　•n个结点可以生成的红黑树的最大高度为2log(n+1) （记住即可）（尝试解释：对于一颗全黑满树，挑一条路径，两两黑结点之间插入红结点以增加树高，最后得到的树就是达到该树高对结点量需求最少的树。此时树高为h，黑结点数为2^(h/2)-1，红结点数为h，该结点需求最少的树拥有2^(h/2)-1+h个结点。）
　　•AVL树与红黑树的查找，删除，插入的时间复杂度都为O(logn)。
　　3.3 插入：（直接插入+维护不红红条件）
　　a.插入结点。若插入结点将作为根结点，设为黑色，结束，否则设为红色（维护“黑路同”条件）。
　　b.看父结点是否是黑色，黑色表明不与“不红红”冲突，结束，否则进行接下来的维护操作。
　　c.看叔结点的颜色决定维护操作：
　　　c.1 叔结点为红色：叔父爷变色，将爷视为插入结点重复a步骤。
　　　c.2 叔结点为黑色或不存在：旋转+染色。旋转同AVL树，将其爷节点视为“最小不平衡子树根结点”r，将其父结点视为r的“最高子树”。染色时LL与RR旋，则父爷换色，LR与RL旋，则爷与插入结点换色。
　　•红黑树的任意子树不一定为红黑树，因为不一定满足根结点必黑的条件。
　　•红黑树的删除操作的旋转次数可能超过两次，插入操作最多两次旋转。

4.B树

　　4.1 树形/时间复杂度分析
　　给定关键字数n，树的阶数m。
　　•为了树尽量矮，规定每个非根结点至少有⌈m/2⌉个子树，至少包含⌈m/2⌉-1个关键字。根结点若不为叶节点至少有一个关键字即两个子树。
　　•树的高度最大时，根结点仅包含一个关键字，每个非根结点仅包含(⌈m/2⌉-1)个关键字，射出⌈m/2⌉条边（即充分伸高），关键字数为n = f(h) = 1+(⌈m/2⌉-1)（2+2⌈m/2⌉+2⌈m/2⌉^2+2⌈m/2⌉^3...+2⌈m/2⌉^(h-2))。那么可以求得不同h下所需要的最少关键字。题目给你关键字数numkey，仅需列出不同h需要的最少关键字数，当列出f(h0)<numkey而f(h0+1)>numkey时，numkey才够组成h0高度的B树，h0就是给定关键字下最高树高。
　　•树的高度最小时，每个结点包括根结点都有(m-1)个关键字，射出m条边（即充分长胖），关键字数n = f(h) = (m-1)(1+m+m^2+m^(h-1))，那么可以求得不同h下可容纳的最多关键字。题目给你关键字数numkey，仅需列出不同h支持的最多关键字数，当列出f(h0-1)<numkey而f(h0)>numkey时，h0才能容纳这么多的关键字，那么h0就是给定关键字下最低树高。
　　•实际做题时上述求最高最低树高的，现推太慢，太耗时间，现在花时间背公式考场少花时间。
　　•n个关键字的B数必定具有n-1个叶节点。因为n个关键字将(-∞,+∞)分为n+1个区间，落在这些区间上都是失败，落在分割点上都是成功的，失败结点即叶结点。
　　•408的叶节点指的是终端结点而非虚构NULL失败结点。

　　4.2 插入
　　将待插入关键字插入底部的终端结点，若插入后该终端结点的关键字超出m-1，即该结点目前拥有m个关键字。
　　若m为偶数，前m/2-1个留在结点，m/2号关键字插入到父结点，后面剩下的m/2个关键字新分配一个兄弟结点存储。
　　若m是奇数，则取中间的关键字插入到父结点，其左右各成一个结点。父结点若超了，则进行同样的操作。
　　ps:只要记住谁给父结点就行，m为偶数是刚好一半，m为奇数是刚好中间。

　　4.3删除
　　a.将待删除关键字直接删除。
　　b.被删关键字不在终端结点。用其直接前驱或后继代替它在该结点的位置即可。以c方式删除在终端结点中的直接前驱或后继。
　　c.被删关键字在终端结点。
　　　c.1 此时终端结点关键字数量满足最低要求⌈m/2⌉-1个，则无需任何操作。
　　　c.2 此时终端结点关键字数量低于最低要求⌈m/2⌉-1个，则需要看左右兄弟。若右兄弟够借，则父给它，兄给父。若左右兄弟都不够借，则父给它，它与一个兄弟合并。
　　d.最后若父结点是根结点且为空，抹去；不是根结点但关键字数低于限制，将该结点视为被删关键字的结点从b操作开始。

5.B+树

　　•广泛用于磁盘文件系统，磁盘的一个块即B+树的一个结点。所有记录指针都存在终端结点上，其余非终端结点存储的都是索引指针。这样使得一个磁盘块能够存更多的关键字索引，使B+树的阶达到最大。从而使B+树的高度最小，磁头在块之间转换的次数非常稳定，且最少。（B树也有概率很少，即待查关键字在树的前几行，但是由于B树每个关键字都附带一个很大的记录指针，树的阶明显小，树高明显更大，导致性能很多情况下是很差的。）