您的位置: 首页  >  文章  >  面试复习笔记

面试复习笔记

分类: 文章 • 2022-10-07 16:30:07

面试复习笔记

一、数据结构

1. 杂谈

  • 循环队列的顺序表中，为什么要空一个位置？
    这是为了用来区分队空与队满的情况。如果不空一个位置，则判断队空和队满的条件是一样的。
    循环队列是为了解决“假溢出”现象。
  • 有哪些查找算法
    基于Hash表的查找
    蛮力查找（顺序查找）
    基于有序表的二分查找
    字符串的查找　
    基于树的查找

2. 哈夫曼树

  • 定义
    给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树 。
  • 特点
    ① 权值越大的结点，距离根节点越近； ② 树中没有度为一的结点。
  • 构造方法
void HuffmanTree(element[] huffTree. int[] weight. int n){
	//初始化结构
	for(int i = 0; i < 2*n-1; i++){ //n个叶子节点的哈夫曼树，最多有2*n-1个节点，全在底层
		huffTree[i].parent = -1;
		huffTree[i].lchild = -1;
		huffTree[i].rchild = -1;
	}
	//赋初始权值
	for(int i = 0; i < n; i++){ //n个值
		huffTree[i].weight = weight[i];
	}
	int min1, min2;
	for(int k = n; k < 2*n-1; k++){
		select(huffTree, min1, min2); //从huffman tree中找到最小的两个元素
		huffTree[k].weight = huffTree[min1].weight + huffTree[min2].weight;
		huffTree[min1].parent = k;
		huffTree[min2].parent = k;
		huffTree[k].lchild = min1;
		huffTree[k].rchild = min2;
	}
}
  • 存储结构
    面试复习笔记

3. 哈希冲突

  • 定义
    根据关键码值(Key value)而直接进行访问的数据结构。根据给定的关键字来计算出关键字在表中的地址，以加快查找的速度。

  • 冲突
    指的是多个关键字映射同一个地址的情况。

  • 解决冲突
    （1）开放定址法
    线性探测再散列、二次探测再散列、伪随机探测再散列（事先设置一个伪随机序列）
    （2）再哈希法
    （3）链地址法（根据装填因子来更新表长）
    （4）建立公共溢出区

  • 常见的哈希函数
    直接定址法（直接取关键字），数字分析法（取若干位），平方取中法，分段叠加，除留余数法，伪随机数法（构造哈希函数）。

4. 图的存储方式

① 邻接矩阵：是图的顺序存储结构，用两个数组分别存储数据元素（顶点）信息和数据元素之间的关系（边/弧）的信息。图的邻接矩阵表示是唯一的，无向图的邻接矩阵是对称的。
② 邻接表：是图的链式存储结构，由单链表的表头形成的顶点表和单链表其余结点所形成的边表两部分组成。
③ 十字链表：有向图的另一种链式存储结构。
④ 邻接多重表：无向图的链式存储结构。

5. B-树

  • 一棵m阶的B-树的定义(递归)：
    或者是一棵空树，或者是满足下列特性的m叉树；
    （1）树中每个结点至多有m棵子树；
    （2）若根结点不是叶子结点，则至少有两棵子树；
    （3）除根之外的所有非终端结点至少有m/2向上取整棵子树，至多有m棵子树；
    （4）所有的非终端结点中包含下列信息数据(n, P0, K1, P1, K2, P2,…, Kn , Pn)：关键字个数、关键字i（记录+地址）、指向子树根节点的指针i；
    （5）所有叶子结点都出现在同一层，叶子结点可看作Null节点 。
    面试复习笔记
    注意：B树即二叉搜索树，B-树是多路搜索树。

6. B+树

B+树不是树！是B-树的一个变型树。

  • 区别
    有n棵子树的结点中含有n个关键字;
    所有叶子结点中包含了全部关键字的信息及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
    所有非终端结点可以看成是索引部分，结点中仅含有其子树中的最大或最小关键字。

  • 结构
    B-树索引: （索引块）

    • B-树的指针是稀疏索引，指向块号；
    • B-树仅起路标的作用，B-树中的索引记录项可能实际并不存在；

    顺序集合：（数据块）

    • 存放真实的记录索引；
    • 一般组织成稠密索引，指针指向记录地址。

  • 查找方式
    （横向）顺序查找：从顺序集链头开始；
    （纵向）随即查找：从B-树的根开始。
    面试复习笔记

7. 堆

堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足：任何一个非叶节点的值都不大于（或不小于）其左右子树的结点的值。
应用：堆排序
注意：被问及时，应明确是数据结构里的堆，还是操作系统里的堆。

二、计算机网络

三、操作系统

  1. 什么是进程（Process）和线程（Thread）？有何区别？

  • 进程
    定义：进程是对运行时程序的封装，是系统进行资源调度和分配的基本单位，实现了操作系统的并发。
    基本特征：

    • 动态性：动态产生、动态消亡；
    • 并发性：同其它进程并发执行；
    • 独立性：独立运行的活动实体；
    • 异步性：进程间相互制约，按各自独立的不可预知的速度推进。

  • 线程
    线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发；
    线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器，一组寄存器和栈），但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
    一个线程可以创建和撤销另一个线程；同一个进程中的多个线程之间可以并发执行。

一个程序至少有一个进程，一个进程至少有一个线程，线程依赖于进程而存在；进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。

  1. Windows下的内存是如何管理的？
    Windows提供了3种方法来进行内存管理：
    虚拟内存，最适合用来管理大型对象或者结构数组；
    内存映射文件，最适合用来管理大型数据流（通常来自文件）以及在单个计算机上运行多个进程之间共享数据；
    内存堆栈，最适合用来管理大量的小对象。

  2. 描述实时系统的基本特性
    在特定时间内完成特定的任务，实时性与可靠性。
    指当外界事件或数据产生时，能够接受并以足够快的速度予以处理，其处理的结果又能在规定的时间之内来控制生产过程或对处理系统做出快速响应，调度一切可利用的资源完成实时任务，并控制所有实时任务协调一致运行的操作系统。

  3. 中断和轮询的特点。

  • 轮询/程控输入输出
    由CPU定时发出询问，依序询问每一个周边设备是否需要其服务，有即给予服务，服务结束后再问下一个周边，接着不断周而复始。
    特点：轮询要比I/O设备的速度要快得多、I/O设备的数量有限、轮询占据CPU相当一部分处理时间。效率低，等待时间很长，CPU利用率不高
  • 程序中断/中断
    指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动停止正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行。
    特点：容易遗漏一些问题，CPU利用率高
  1. 什么是临界区？如何解决冲突？
  • 定义
    每个进程中访问临界资源（一次仅允许一个进程使用的资源）的那段程序称为临界区，每次只准许一个进程进入临界区，进入后不允许其他进程进入。
  • 措施
    • 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入；
    • 任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待；
    • 进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区；
    • 如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

  1. 说说分段和分页
    段式存储管理是一种符合用户视角的内存分配管理方案。在段式存储管理中，将程序的地址空间划分为若干段（segment），如代码段，数据段，堆栈段；这样每个进程有一个二维地址空间，相互独立，互不干扰。段式管理的优点是：没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）
    页式存储管理方案是一种用户视角内存与物理内存相分离的内存分配管理方案。在页式存储管理中，将程序的逻辑地址划分为固定大小的页（page），而物理内存划分为同样大小的帧，程序加载时，可以将任意一页放入内存中任意一个帧，这些帧不必连续，从而实现了离散分离。页式存储管理的优点是：没有外碎片（因为页的大小固定），但会产生内碎片（一个页可能填充不满）。
    两者的不同点：
    目的不同：分页是由于系统管理的需要而不是用户的需要，它是信息的物理单位；分段的目的是为了能更好地满足用户的需要，它是信息的逻辑单位，它含有一组其意义相对完整的信息；
    大小不同：页的大小固定且由系统决定，而段的长度却不固定，由其所完成的功能决定；
    地址空间不同： 段向用户提供二维地址空间；页向用户提供的是一维地址空间；
    信息共享：段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制；
    内存碎片：页式存储管理的优点是没有外碎片（因为页的大小固定），但会产生内碎片（一个页可能填充不满）；而段式管理的优点是没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）。

  2. 进程通信有哪些方式？

  • 管道（pipe）及命名管道（named pipe）：
    管道（局域网）可用于具有亲缘关系的父子进程间（共性大）的通信；有名管道（外网）除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信，但是要指明发送方和接收方；
  • 信号（signal）：
    信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；
  • 消息队列：
    消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；
  • 共享内存：
    可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等；
  • 信号量：
    主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段；
  • 套接字：
    这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。

  1. 说出你所知道的保持进程同步的方法?
    进程间同步的主要方法有内存屏障，互斥锁，信号量和锁，管程，消息，管道。

  2. makefile文件的作用是什么？
    一个工程中的源文件不计数，其按类型、功能、模块分别放在若干个目录中，makefile定义了一系列的规则来指定，哪些文件需要先编译，哪些文件需要后编译，哪些文件需要重新编译，甚至于进行更复杂的功能操作，因为 makefile就像一个Shell脚本一样，其中也可以执行操作系统的命令。
    makefile带来的好处就是——“自动化编译”，一旦写好，只需要一个make命令，整个工程完全自动编译，极大的提高了软件开发的效率。make是一个命令工具，是一个解释makefile中指令的命令工具，一般来说，大多数的IDE都有这个命令，比如：Delphi的make，Visual C++的nmake，Linux下GNU的make。可见，makefile都成为了一种在工程方面的编译方法。

  3. CPU在上电后，进入操作系统的main()之前必须做什么？
    加电后，会触发CPU的reset信号，导致CPU复位，然后CPU会跳到(arm下0x00000000,x86下0xfffffff0)执行指令。主要是做CPU初始化，确定CPU的工作模式，mmu初始化。建立页表段表，初始化中孤单控制器和中断向量表，初始化输入和输出，初始化nandflash，把OS的TEXT区加载到sdram，然后跳转到sdram的main()

  4. 什么是中断？中断时CPU做什么工作？
    中断是指在计算机执行期间，系统内发生任何非寻常的或非预期的急需处理事件，使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序。待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。

  5. 存储过程是什么？有什么用？有什么优点？
    存储过程（Stored Procedure）是一组为了完成特定功能的SQL 语句集，经编译后存储在数据库中。用户通过指定存储过程的名字并给出参数（如果该存储过程带有参数）来执行它。存储过程是SQL 语句和可选控制流语句的预编译集合，以一个名称存储并作为一个单元处理。存储过程存储在数据库内，可由应用程序通过一个调用执行，而且允许用户声明变量、有条件执行以及其它强大的编程功能。存储过程在创建时即在服务器上进行编译，所以执行起来比单个SQL语句快。
    存储过程的优点：
    存储过程只在创造时进行编译，以后每次执行存储过程都不需再重新编译，而一般SQL语句每执行一次就编译一次,所以使用存储过程可提高数据库执行速度；
    当对数据库进行复杂操作时(如对多个表进行Update, Insert, Query, Delete时），可将此复杂操作用存储过程封装起来与数据库提供的事务处理结合一起使用；
    存储过程可以重复使用,可减少数据库开发人员的工作量；
    安全性高,可设定只有某此用户才具有对指定存储过程的使用权。
    存储过程的缺点：
    如果更改范围大到需要对输入存储过程的参数进行更改，或者要更改由其返回的数据，则您仍需要更新程序集中的代码以添加参数、更新 GetValue() 调用，等等，这时候估计比较繁琐了。
    可移植性差。由于存储过程将应用程序绑定到 SQL Server，因此使用存储过程封装业务逻辑将限制应用程序的可移植性。

  6. 操作系统的内容分为几块吗？什么叫做虚拟内存？他和主存的关系如何？内存管理属于操作系统的内容吗？
    操作系统的主要组成部分：进程和线程的管理，存储管理，设备管理，文件管理。
    虚拟内存是一些系统页文件，存放在磁盘上，每个系统页文件大小也为4K，物理内存也被分页，每个页大小也为4K，这样虚拟页文件和物理内存页就可以对应，实际上虚拟内存就是用于物理内存的临时存放的磁盘空间。
    页文件就是内存页，物理内存中每页叫物理页，磁盘上的页文件叫虚拟页，物理页+虚拟页就是系统所以使用的页文件的总和。
    属于。

  7. 进程有哪几种状态？
    就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源；
    运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数；
    阻塞状态： 进程等待某种条件，在条件满足之前无法执行；

  8. OS中如何实现物理地址到逻辑地址的转换?
    CPU要利用其段式内存管理单元，先将逻辑地址转换成一个线程地址，再利用其页式内存管理单元，转换为最终物理地址。

  9. 堆和栈的区别？
    栈区，由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
    堆：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式是类似于链表。可能用到的关键字如下：new、malloc、delete、free等等。

  10. 线程是否具有相同的堆栈？dll是否有独立的堆栈？
    每个线程有自己的堆栈。
    DLL中有没有独立的堆栈，这个问题不好回答，或者说这个问题本身是否有问题。因为DLL中的代码是被某些线程所执行，只有线程拥有堆栈，如果DLL中的代码是EXE中的线程所调用，那么这个时候是不是说这个DLL没有自己独立的堆栈？如果DLL中的代码是由DLL自己创建的线程所执行，那么是不是说DLL有独立的堆栈？
    以上讲的是堆栈，如果对于堆来说，每个DLL有自己的堆，所以如果是从DLL中动态分配的内存，最好是从DLL中删除，如果你从DLL中分配内存，然后在EXE中，或者另外一个DLL中删除，很有可能导致程序崩溃。

  11. 网络编程中设计并发服务器，使用“多进程”与“多线程”，请问有什么区别？
    进程：子进程是父进程的复制品。子进程获得父进程数据空间、堆和栈的复制品。
    线程：相对与进程而言，线程是一个更加接近与执行体的概念，它可以与同进程的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。
    两者都可以提高程序的并发度，提高程序运行效率和响应时间。
    线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源管理和保护；而进程正相反。同时，线程适合于在SMP机器上运行，而进程则可以跨机器迁移。

  12. 解释一下分页式管理.
    用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。

  13. 解释一下P操作与V操作
    P就是请求资源，V就是释放资源

  14. 什么是缓冲区溢出？有什么危害？其原因是什么？
    缓冲区溢出是指当计算机向缓冲区内填充数据位数时超过了缓冲区本身的容量溢的数据覆盖在合法数据上,
    危害：在当前网络与分布式系统安全中，被广泛利用的50%以上都是缓冲区溢出，其中最著名的例子是1988年利用fingerd漏洞的蠕虫。而缓冲区溢出中，最为危险的是堆栈溢出，因为入侵者可以利用堆栈溢出，在函数返回时改变返回程序的地址，让其跳转到任意地址，带来的危害一种是程序崩溃导致拒绝服务，另外一种就是跳转并且执行一段恶意代码，比如得到shell，然后为所欲为。通过往程序的缓冲区写超出其长度的内容，造成缓冲区的溢出，从而破坏程序的堆栈，使程序转而执行其它指令，以达到攻击的目的。
    造成缓冲区溢出的原因是程序中没有仔细检查用户输入的参数

  15. 什么是死锁？其条件是什么？怎样避免死锁？
    在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲，就是两个或多个进程无限期的阻塞、相互等待的一种状态。
    死锁产生的原因：
    系统资源不足；
    进程运行推进的顺序不合适；
    资源分配不当。
    产生死锁的必要条件：
    互斥（mutual exclusion），一个资源每次只能被一个进程使用；
    占有且等待（hold and wait）/请求和保持，一个进程必须占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有；
    不可抢占（no preemption），进程已获得的资源，在未使用完之前，不能强行剥夺；
    环形等待（circular wait），若干进程之间形成一种首尾相接的循环等待资源关系。
    死锁的处理基本策略和常用方法
    解决死锁的基本方法主要有 预防死锁、避免死锁、检测死锁、解除死锁 、鸵鸟策略 等。
    (1).死锁预防
    死锁预防的基本思想是 只要确保死锁发生的四个必要条件中至少有一个不成立，就能预防死锁的发生，具体方法包括：

打破互斥条件：允许进程同时访问某些资源。但是，有些资源是不能被多个进程所共享的，这是由资源本身属性所决定的，因此，这种办法通常并无实用价值。
打破占有并等待条件：可以实行资源预先分配策略(进程在运行前一次性向系统申请它所需要的全部资源，若所需全部资源得不到满足，则不分配任何资源，此进程暂不运行；只有当系统能满足当前进程所需的全部资源时，才一次性将所申请资源全部分配给该线程)或者只允许进程在没有占用资源时才可以申请资源（一个进程可申请一些资源并使用它们，但是在当前进程申请更多资源之前，它必须全部释放当前所占有的资源）。但是这种策略也存在一些缺点：在很多情况下，无法预知一个进程执行前所需的全部资源，因为进程是动态执行的，不可预知的；同时，会降低资源利用率，导致降低了进程的并发性。
打破非抢占条件：允许进程强行从占有者哪里夺取某些资源。也就是说，但一个进程占有了一部分资源，在其申请新的资源且得不到满足时，它必须释放所有占有的资源以便让其它线程使用。这种预防死锁的方式实现起来困难，会降低系统性能。
打破循环等待条件：实行资源有序分配策略。对所有资源排序编号，所有进程对资源的请求必须严格按资源序号递增的顺序提出，即只有占用了小号资源才能申请大号资源，这样就不回产生环路，预防死锁的发生。
(2). 死锁避免的基本思想

死锁避免的基本思想是动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。资源分配图算法和银行家算法是两种经典的死锁避免的算法，其可以确保系统始终处于安全状态。其中，资源分配图算法应用场景为每种资源类型只有一个实例(申请边，分配边，需求边，不形成环才允许分配)，而银行家算法应用于每种资源类型可以有多个实例的场景。
(3). 死锁解除

死锁解除的常用两种方法为进程终止和资源抢占。所谓进程终止是指简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；所谓资源抢占是指从一个或多个死锁进程那里抢占一个或多个资源，此时必须考虑三个问题：
(I). 选择一个牺牲品
(II). 回滚：回滚到安全状态
(III). 饥饿（在代价因素中加上回滚次数，回滚的越多则越不可能继续被作为牺牲品，避免一个进程总是被回滚）

  1. 同步通讯效率为什么高于异步通信
    因为同步通信用一个公共的时钟信号进行同步。

  2. 操作系统中进程调度策略有哪几种？
    FCFS(先来先服务，队列实现，非抢占的)：先请求CPU的进程先分配到CPU
    SJF(最短作业优先调度算法)：平均等待时间最短，但难以知道下一个CPU区间长度
    优先级调度算法(可以是抢占的，也可以是非抢占的)：优先级越高越先分配到CPU，相同优先级先到先服务，存在的主要问题是：低优先级进程无穷等待CPU，会导致无穷阻塞或饥饿；解决方案：老化
    时间片轮转调度算法(可抢占的)：队列中没有进程被分配超过一个时间片的CPU时间，除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片，那么该进程就被抢占并放回就绪队列。
    多级队列调度算法：将就绪队列分成多个独立的队列，每个队列都有自己的调度算法，队列之间采用固定优先级抢占调度。其中，一个进程根据自身属性被永久地分配到一个队列中。
    多级反馈队列调度算法：与多级队列调度算法相比，其允许进程在队列之间移动：若进程使用过多CPU时间，那么它会被转移到更低的优先级队列；在较低优先级队列等待时间过长的进程会被转移到更高优先级队列，以防止饥饿发生。

  3. 什么是虚拟内存？
    虚拟内存允许执行进程不必完全在内存中。虚拟内存的基本思想是：每个进程拥有独立的地址空间，这个空间被分为大小相等的多个块，称为页(Page)，每个页都是一段连续的地址。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻进行必要的映射；当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。这样，对于进程而言，逻辑上似乎有很大的内存空间，实际上其中一部分对应物理内存上的一块(称为帧，通常页和帧大小相等)，还有一些没加载在内存中的对应在硬盘上。
    注意，请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的，通过请求实现内存与外存的信息置换。
    页面置换算法
    FIFO先进先出算法：在操作系统中经常被用到，比如作业调度（主要实现简单，很容易想到）；
    LRU（Least recently use）最近最少使用算法：根据使用时间到现在的长短来判断；
    LFU（Least frequently use）最少使用次数算法：根据使用次数来判断；
    OPT（Optimal replacement）最优置换算法：理论的最优，理论；就是要保证置换出去的是不再被使用的页，或者是在实际内存中最晚使用的算法。
    虚拟内存的应用与优点
    虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把CPU交给另一个进程使用。虚拟内存的使用可以带来以下好处：

在内存中可以保留多个进程，系统并发度提高
解除了用户与内存之间的紧密约束，进程可以比内存的全部空间还大

  1. 颠簸
    颠簸本质上是指频繁的页调度行为，具体来讲，进程发生缺页中断，这时，必须置换某一页。然而，其他所有的页都在使用，它置换一个页，但又立刻再次需要这个页。因此，会不断产生缺页中断，导致整个系统的效率急剧下降，这种现象称为颠簸（抖动）。

内存颠簸的解决策略包括：

如果是因为页面替换策略失误，可以修改替换算法来解决这个问题；
如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量；
否则，还剩下两个办法：终止该进程或增加物理内存容量。

  1. 局部型原理
    时间上的局部性：最近被访问的页在不久的将来还会被访问；

空间上的局部性：内存中被访问的页周围的页也很可能被访问。

四、数据库

  1. 索引
    索引是一种数据结构，索引基本上是用来存储列值的数据结构，同时存储了指向表中的相应行的指针。指针是指一块内存区域， 该内存区域记录的是对硬盘上记录的相应行的数据的引用。
  • 类型（MySQL，*不是）
    普通索引：没有任何限制；
    唯一索引：索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一；
    主键索引：一个表只能有一个主键，不允许有空值；
    组合索引：多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用；
    全文索引：用来查找文本中的关键字，而不是直接与索引中的值相比较。
    *（非）聚集索引：表中记录的物理顺序与键值的索引顺序相同。一个表只能有一个聚集索引。
  • 实现
    B-树（Sql server ,Oracle）、B+树（MySQL）、哈希表、Trie树、R-树（空间问题）、位图索引（布尔值）。
  • 哈希索引的缺点
    是无序的，对于查询“小于40”的情况无能为力。故不常作为数据库索引结构。
  • 索引的缺点
    索引会占用空间 ；性能损失，尤其在更新索引时。
  • Oracle分区（partition）
    range分区（范围值）、hash分区、list分区（具体值）、复合分区 + 分区索引（local、global）

五、组成原理

六、Linux

七、Java

相关推荐