面试总结（一）

1、红黑树与val树对比

红黑树和AVL树都是最常用的平衡二叉搜索树，它们支持插入，删除和查找保证。0(1ogN) time 
但是，两者之间有以下几点比较:
●AVL树更加严格平衡，因此可以提供更快的查找效果。因此，对于查找密集型任务，使用AVL树。 型任务，使用avl树.
●对于插入密集型任务，请使用红黑树。 
●AVL树在每个节点存储平衡因子。但是，如果我们知道将插入树中 AVL树在每个节点存储平衡因子，我们可以使用键的符号位来存储红黑树的颜色信息。因此，在这种情况下，与AVL树相比更有效和有用
●通常，AVL树的旋转比红黑树的旋转更难实现和调试。 
两者在其应用基础上的一些不同点是: 
红黑树更通用。它们在添加，删除和查找方面表现相对较好，但AVL树的查找速度更 快，代价是添加/删除速度较慢。

红黑树用于：
   java:         java.util.TreeMap   java.util.TreeSet
   c++STL:    map   multimap   multiset
   Linux内核: 完全公平的调度程序，Linux/rbtree.h

AVL树的应用：
   插入删除不是那么频繁，经常查找存在的项目.

2、操作系统用户态与内核态

什么是用户态和内核态

所谓的用户态、内核态，实际上是处理器（cpu）的一种状态，在 cpu 状态字里面用 1bit 表示

什么是用户态？
　　也叫普通态，cpu 访问资源有限
　　用户态的几个特点
　　　　cpu 访问资源有限
　　　　程序可靠性、安全性要求低
　　　　程序编写维护比较简单
什么是内核态
　　也叫特权态，cpu 可以访问计算机的任何资源
　　内核态的特点
　　　　cpu 可以访问任何资源
　　　　程序可靠性、安全性要求高
　　　　编写维护成本比较高
为什么需要有用户态和内核态
　　想象一下，如果一个国家的所有人都能获得国家的机密资料、控制国家资源，那这个国家也就离崩溃不远了。
　　操作系统也是如此，所以我们要限制不用的程序访问资源的权限。

操作系统是如何控制不同态的权限的
　　要控制权限，必须要对程序发出的每一条指令进行检查。而这种检查被称为 地址翻译，这里不详细展开。内核态程序通过绕过地址翻译执行特权指令，从而访问所有资源。

程序应该运行在用户态还是内核态？
　　用户态
　　　　能运行在用户态就运行在用户态
　　内核态
　　　　涉及用户数据和应用的操作
　　　　牵扯到计算机本体的操作
　　　　对时序要求比较高的操作
用户态如何切换到内核态？
　　用户态程序 陷入 到内核态有 3 种方法：
　　　　系统调用
　　　　外围设备中断
　　　　异常
　　具体处理过程：
　　　　通过 软中断 切换

内核态如何切换到用户态？
　　设置程序转台字

3、epoll 原理

https://www.cnblogs.com/xiao-xue-di/p/9942414.html

1创建epoll对象
　　当某个进程调用epoll_create方法时，内核会创建一个eventpoll对象（也就是程序中epfd所代表的对象）。eventpoll对象也是文件系统中的一员，和socket一样，它也会有等待队列（有线程会等待其事件触发，比如调用epoll_wait的线程就会阻塞在其上）。

2内核创建eventpoll对象
　　创建一个代表该epoll的eventpoll对象是必须的，因为内核要维护“就绪列表”等数据，“就绪列表”可以作为eventpoll的成员。

3维护监视列表
　　创建epoll对象后，可以用epoll_ctl添加或删除所要监听的socket。以添加socket为例,如果通过epoll_ctl添加sock1、sock2和sock3的监视，内核会将eventpoll添加到这三个socket的等待队列中。

4添加所要监听的socket
　　当socket收到数据后，中断程序会操作eventpoll对象，而不是直接操作进程（也就是调用epoll的进程）。

5接收数据
　　当socket收到数据后，中断程序会给eventpoll的“就绪列表”添加socket引用。

6给就绪列表添加引用
　　eventpoll对象相当于是socket和进程之间的中介，socket的数据接收并不直接影响进程，而是通过改变eventpoll的就绪列表来改变进程状态。
　　当程序执行到epoll_wait时，如果rdlist已经引用了socket，那么epoll_wait直接返回，如果rdlist为空，阻塞进程。

7阻塞和唤醒进程
　　假设计算机中正在运行进程A和进程B，在某时刻进程A运行到了epoll_wait语句。内核会将进程A放入eventpoll的等待队列中，阻塞进程。

8epoll_wait阻塞进程
　　当socket接收到数据，中断程序一方面修改rdlist，另一方面唤醒eventpoll等待队列中的进程

(1)select==>时间复杂度O(n)

它仅仅知道了，有I/O事件发生了，却并不知道是哪那几个流（可能有一个，多个，甚至全部），我们只能无差别轮询所有流，找出能读出数据，或者写入数据的流，对他们进行操作。所以select具有O(n)的无差别轮询复杂度，同时处理的流越多，无差别轮询时间就越长。

(2)poll==>时间复杂度O(n)

poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态， 但是它没有最大连接数的限制，原因是它是基于链表来存储的.

(3)epoll==>时间复杂度O(1)

epoll可以理解为event poll，不同于忙轮询和无差别轮询，epoll会把哪个流发生了怎样的I/O事件通知我们。所以我们说epoll实际上是事件驱动（每个事件关联上fd）的，此时我们对这些流的操作都是有意义的。（复杂度降低到了O(1)）

select，poll，epoll都是IO多路复用的机制。I/O多路复用就通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。
但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。  

epoll跟select都能提供多路I/O复用的解决方案。在现在的Linux内核里有都能够支持，其中epoll是Linux所特有，而select则应该是POSIX所规定，一般操作系统均有实现

4、gevent 原理

gevent 比起其他框架（比如tornado，twisted）的一个巨大优势就是：用同步的方法（自然没有回调函数）写异步应用，因为同步的方式更接近开发人员的编程思维。
gevent可以用一句话向pythoner阐述：使用多路IO复用对文件描述符的事件监听，从而撬动协程的“透明”切换。这句话说起来容易，但是阐述起来就复杂些：
　　底层（或者说主协程）自然有一个多路IO复用循环（linux上是epoll，unix是kqueue，以下统一用epoll代替描述）
当处理一个socket链接时，就创建一个协程greenlet去处理。
当socket遇到阻塞的时候，比如等待数据的返回或者发送，此时gevent做了很关键的两步：
　　为这个socket的fd在epoll上添加可读或者可写事件回调，而这个回调函数便是 gevent.getcurrent().switch
　　通过 get_hub().switch() 切换到主协程。切换回主协程，去干其他事情了。但是当该socket可读或者可写，
　　epoll自然会调用上述添加的回调函数，从而切换回socket的处理协程，从上次悬挂点接着往下执行。
之所以做到透明，是因为python socket上打了patch。所谓打patch，就是自己实现了一个socket模块替换了python的标准socket模块。
def patch_socket():
　　from gevent import socket
　　_socket = __import__('socket')
　　_socket.socket = socket.socket
　　...
gevent实现的socket模块，比起python的标准socket模块，做了以下修改：
将所有的socket设置成非阻塞。
　　修改关键函数，比如send，recv，发生阻塞（捕获到异常 EWOULDBLOCK）时，在socket的fd添加回调函数，并跳回到主协程。
综上所述，gevent不是没有事件监听回调，而是通过给python socket打patch，使其透明化，最终达到让编程人员用同步的思维去开发。
ps，给python socket打patch，固然好，但是有个小缺点，就是：python c扩展模块中的socket并不受gevent的管制和调度，因此用在gevent中的网络库，都尽量使用纯python库。

5、mysql索引为什么选择b+树

一、二叉查找树(BST)：不平衡

二叉查找树(BST，Binary Search Tree)，也叫二叉排序树，在二叉树的基础上需要满足：任意节点的左子树上所有节点值不大于根节点的值，任意节点的右子树上所有节点值不小于根节点的值。如下是一颗BST(图片来源)。

当需要快速查找时，将数据存储在BST是一种常见的选择，因为此时查询时间取决于树高，平均时间复杂度是O(lgn)。然而，BST可能长歪而变得不平衡，如下图所示(图片来源)，此时BST退化为链表，时间复杂度退化为O(n)。

为了解决这个问题，引入了平衡二叉树。

二、平衡二叉树(AVL)：旋转耗时

AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。

AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。

由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

三、红黑树：树太高

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看，红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一，且节点颜色的划分需要满足特定的规则(具体规则略)。红黑树示例如下（图片来源）：

与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。总的来说，红黑树的统计性能高于AVL。

因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。

对于数据在内存中的情况（如上述的TreeMap和HashMap），红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严重影响性能。

四、B树：为磁盘而生

B树也称B-树(其中-不是减号)，是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，B树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。

定义B树最重要的概念是阶数(Order)，对于一颗m阶B树，需要满足以下条件：

每个节点最多包含 m 个子节点。
如果根节点包含子节点，则至少包含 2 个子节点；除根节点外，每个非叶节点至少包含 m/2 个子节点。
拥有 k 个子节点的非叶节点将包含 k - 1 条记录。
所有叶节点都在同一层中。

可以看出，B树的定义，主要是对非叶结点的子节点数量和记录数量的限制。

下图是一个3阶B树的例子（图片来源）：

B树的优势除了树高小，还有对访问局部性原理的利用。所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。

B树在数据库中有一些应用，如mongodb的索引使用了B树结构。但是在很多数据库应用中，使用了是B树的变种B+树。

五、B+树

B+树也是多路平衡查找树，其与B树的区别主要在于：

B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现——一定会在叶节点出现，也可能在非叶节点重复出现。
B+树的叶节点之间通过双向链表链接。
B树中的非叶节点，记录数比子节点个数少1；而B+树中记录数与子节点个数相同。

由此，B+树与B树相比，有以下优势：

更少的IO次数：B+树的非叶节点只包含键，而不包含真实数据，因此每个节点存储的记录个数比B数多很多（即阶m更大），因此B+树的高度更低，访问时所需要的IO次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
更适于范围查询：在B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可。
更稳定的查询效率：B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

B+树也存在劣势：由于键会重复出现，因此会占用更多的空间。但是与带来的性能优势相比，空间劣势往往可以接受，因此B+树的在数据库中的使用比B树更加广泛。

六、感受B+树的威力

前面说到，B树/B+树与红黑树等二叉树相比，最大的优势在于树高更小。实际上，对于Innodb的B+索引来说，树的高度一般在2-4层。下面来进行一些具体的估算。

树的高度是由阶数决定的，阶数越大树越矮；而阶数的大小又取决于每个节点可以存储多少条记录。Innodb中每个节点使用一个页(page)，页的大小为16KB，其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等)，大多数空间都用来存储数据。

对于非叶节点，记录只包含索引的键和指向下一层节点的指针。假设每个非叶节点页面存储1000条记录，则每条记录大约占用16字节；当索引是整型或较短的字符串时，这个假设是合理的。延伸一下，我们经常听到建议说索引列长度不应过大，原因就在这里：索引列太长，每个节点包含的记录数太少，会导致树太高，索引的效果会大打折扣，而且索引还会浪费更多的空间。
对于叶节点，记录包含了索引的键和值(值可能是行的主键、一行完整数据等，具体见前文)，数据量更大。这里假设每个叶节点页面存储100条记录(实际上，当索引为聚簇索引时，这个数字可能不足100；当索引为辅助索引时，这个数字可能远大于100；可以根据实际情况进行估算)。

对于一颗3层B+树，第一层(根节点)有1个页面，可以存储1000条记录；第二层有1000个页面，可以存储1000*1000条记录；第三层(叶节点)有1000*1000个页面，每个页面可以存储100条记录，因此可以存储1000*1000*100条记录，即1亿条。而对于二叉树，存储1亿条记录则需要26层左右。

七、总结

最后，总结一下各种树解决的问题以及面临的新问题：

1) 二叉查找树(BST)：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表；

2) 平衡二叉树(AVL)：通过旋转解决了平衡的问题，但是旋转操作效率太低；

3) 红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多；

4) B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题；

5) B+树：在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。

6、线程之间通信

7、asyncio

https://www.cnblogs.com/xiao-xue-di/p/10273920.html