后端必备知识

进程、线程、协程

进程

(1)进程状态

1.创建状态(new) ：进程正在被创建，尚未到就绪状态。
2.就绪状态(ready) ：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。
3.运行状态(running) ：进程正在处理器上上运行(单核CPU下任意时刻只有一个进程处于运行状态)。
4.阻塞状态(waiting) ：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。
5.结束状态(terminated) ：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。

(2)进程调度方式

• 非抢占方式 ： 把处理机分配给某进程后，就一直让它运行下去，直至完成。或者发生阻塞时（比如 I/O操作引起的阻塞，或者执行了block阻塞原语），才把处理机分配给其它进程。
• 抢占方式：优先权原则、短进程优先原则、时间片原则

抢占方式又细分为：
轮转调度算法： 基于时间片的轮转。(当CPU时间片用完后，或者进程执行完后，开始切换下一个进程 )
优先级调度算法： 将处理机分配给就绪队列中优先级最高的进程。也分为抢占式 和 非抢占式。抢占式可以中断正在运行的低级进程，运行新来的优先级高的进程。非抢占式不会中断正在运行的低优先级的进程。
多队列调度算法： 多个就绪队列。
多级反馈队列调度算法：

(3)进程调度算法

1、时间片轮转调度算法（RR）：给每个进程固定的执行时间，根据进程到达的先后顺序让进程在单位时间片内执行，执行完成后便调度下一个进程执行，时间片轮转调度不考虑进程等待时间和执行时间，属于抢占式调度。优点是兼顾长短作业；缺点是平均等待时间较长，上下文切换较费时。适用于分时系统。

2、先来先服务调度算法（FCFS）：根据进程到达的先后顺序执行进程，不考虑等待时间和执行时间，会产生饥饿现象。属于非抢占式调度，优点是公平，实现简单；缺点是不利于短作业。

3、优先级调度算法（HPF）：在进程等待队列中选择优先级最高的来执行。

4、多级反馈队列调度算法：将时间片轮转与优先级调度相结合，把进程按优先级分成不同的队列，先按优先级调度，优先级相同的，按时间片轮转。优点是兼顾长短作业，有较好的响应时间，可行性强，适用于各种作业环境。

5、高响应比优先调度算法：根据“”这个公式得到的响应比来进行调度。高响应比优先算法在等待时间相同的情况下，作业执行的时间越短，响应比越高，满足段任务优先，同时响应比会随着等待时间增加而变大，优先级会提高，能够避免饥饿现象。优点是兼顾长短作业，缺点是计算响应比开销大，适用于批处理系统。

线程

(1)线程状态

1.NEW：新建状态，;此时thread的状态
2.RUNNABLE：运行状态，此时thread的状态，但是处于这个状态的线程并不一定真正执行，可能会存在在等待资源，因此 上也有人将这个状态分为就绪状态和执行状态两种
3.TERMINATED：结束状态，线程执行完之后的状态

异常状态3种：
1.BLOCKED：阻塞状态，通常出现在语句块中，代表着一个线程等待锁
2.WAITING：等待状态，通常出现在，，语句前后
3.TIMED_WAITING：限时等待状态，当前线程的等待时间是有限制的，时间一到线程就会被唤醒，通常出现，，，，

（2）ThreadLocal

往ThreadLocal中set值就是存入了当前线程对象的属性里，而threadLocals的类型是。ThreadLocalMap 可以理解为 ThreadLocal 类实现的定制化的 HashMap。

Java的四种引用(强弱软虚)

跟ThreadLocal有关的有两个引用: 强引用和弱引用。这两个引用就是内存泄漏的重点,ThreadLocalMap中的Entry对象继承了弱引用类，并且在Entry的构造方法中，会以key作为参数传入到父类构造方法,key是以弱引用指向ThreadLocal，这时候垃圾回收器线程运行，发现弱引用就回收，key被回收。ThreadLocalMap里对应的Entry的key会变成null。而ThreadLocalMap里对应的Entry的value则无法被访问到，value作为一个强引用垃圾回收不到也不能被访问，即造成了内存溢出。注意：主动调用remove方法

• 强引用(StrongReference)： 当JVM的内存空间不足时，宁愿抛出OutOfMemoryError使得程序异常终止也不愿意回收具有强引用的存活着的对象。

• 弱引?(WeakReference)：在GC的时候，不管内存空间足不足都会回收这个对象。

• 软引用（SoftReference）：如果内存空间足够，垃圾回收器就不会回收它，如果内存空间不足了，就会回收这些对象的内存。只要垃圾回收器没有回收它，该对象就可以被程序使用。软引用可用来实现内存敏感的高速缓存。

• 虚引用（PhantomReference）：与其他几种引用都不同，虚引用并不会决定对象的生命周期。如果一个对象仅持有虚引用，那么它就和没有任何引用一样，在任何时候都可能被垃圾回收。

虚引用主要用来跟踪对象被垃圾回收的活动。虚引用与软引用和弱引用的一个区别在于：虚引用必须和引用队列（ReferenceQueue）联合使用。当垃 圾回收器准备回收一个对象时，如果发现它还有虚引用，就会在回收对象的内存之前，把这个虚引用加入到与之关联的引用队列中。程序可以通过判断引用队列中是 否已经加入了虚引用，来了解被引用的对象是否将要被垃圾回收。程序如果发现某个虚引用已经被加入到引用队列，那么就可以在所引用的对象的内存被回收之前采取必要的行动。

1.线程模型

参考阅读：线程的实现
线程是CPU调度执行的基本单位，多个线程共享系统为进程分配的资源，又可以被系统独立调度执行。

（1）内核线程模型(Kernel-Level Thread ，KLT)，即一对一线程模型
（2）用户线程模型(User Thread)，即1:N 模型
（3）混合线程模型- 用户线程 + 轻量级进程混合实现, 即N:M 模型

(1)内核线程模型

即完全依赖操作系统内核提供的内核线程(Kernel-Level Thread ，KLT)来实现多线程。在此模型下，线程的切换调度由系统内核完成，系统内核负责将多个线程执行的任务映射到各个CPU中去执行。

缺点：
在此种线程模型下，线程的各种操作以及切换消耗很低，但线程的所有操作都需要在用户态实现，线程的调度实现起来异常复杂，处理器映射更是无法实现。

(3)混合线程模型

混合线程模型是前述两种模型的混合版本，用户线程仍然是在用户态中创建，用户线程的创建、切换和销毁的消耗很低，用户线程的数量不受限制。而LWP在用户线程和内核线程之间充当桥梁，就可以使用操作系统提供的线程调度和处理器映射功能。

Java内存模型定义了8种原子操作来实现上图中的线程内存交互：

原子性、可见性和有序性

• 原子性
  Java内存模型定义了8中原子操作，此外Java内存模型还保证了对于基本数据类型(char、boolean、int等)的操作是原子性的。对于其他类型的数据如若需要更灵活的原子性操作，Java内存模型提供了lock和unlock操作。JVM中使用的两个字节码指令monitorenter和monitorexit即是通过lock和unlock操作来实现的，常使用的synchronized关键字转换成字节码指令后即由monitorenter和monitorexit构成。

• 可见性
  可见性是指当一个线程修改了主内存中变量的值，其他线程可以立即获取这个修改后的新值。只要在工作内存中修改变量之后立即存储到主内存，以及读取一个变量之前强制从主内存刷新变量的值即可保证可见性。volatile关键字即通过上述方法保证多线程操作变量时的可见性，读写直接是主内存。

• 有序性
  有序性是指在同一个线程中的所有操作都是有序执行的，但由于编译器和处理器都可能对指令进行重排序等行为会导致指令执行的顺序不一定是按照代码中的先后顺序执行的，提高程序执行的速度，在多线程中对一个变量的操作就可能会受到指令重排序的影响。volatile关键字包含有禁止指令重排序的作用，因此使用volatile关键字修饰的变量可以保证多线程之间对该变量操作的有序性，保证自己的读写前后插入屏障，使得不会发生指令重排。

2.多线程&线程池

(1)为什么要引入线程池/h3>

每开一个线程都要新建一个Thread对象来处理，这种操作会造成哪些后果呢/p>

1、系统执行多任务时，会为每个任务创建对应的线程，当任务执行结束之后会销毁对应的线程，在这种情况下对象被频繁的创建和销毁。
2、当对线程象被频繁时会占用大量的系统资源，在并发的过程中会造成资源竞争出现问题。大量的创建线程还会造成混乱，没有一个统一的管理机制，容易造成应用卡顿。
3、大量线程对象被频繁销毁，将会频繁出发GC机制，从而降低性能。

引入线程池的好处：
1、重用线程池中的线程，避免因频繁创建和销毁线程造成的性能消耗。
2、更加有效的控制线程的最大并发数，防止线程过多抢占资源造成的系统阻塞。
3、对线程进行有效的管理。

(2)为什么不推荐使用executors创建/h3>

和 都使用了LinkedBlockingQueue。
和允许的创建线程数量为 Integer.MAX_VALUE， 可能会创建大量的线程，从而导致 OOM。

3.IO模型

参考：
LinuxIO模型
Linux五种IO模型

通常用户进程中的一个完整IO分为两阶段：用户进程空间内核空间、内核空间设备空间（磁盘、 络等）
IO分类：内存IO、 络IO和磁盘IO三种，通常所说指的是后两者

IO这里涉及到基本概念：

同步和异步:
阻塞与非阻塞:
同步阻塞/同步非阻塞:
同步阻塞：一个线程必须等待一个方法调用完毕才能继续执行接下来的任务, 但是等待过程中自己处于挂起状态
同步非阻塞：一个线程必须等待一个方法调用完毕才能继续执行接下来的任务, 且在等待过程中还可以执行其他方法
异步阻塞/异步非阻塞:
数据由 socket 设备到用户态经过两次拷贝: 用户进程在读/写外存(socket 设备)上的数据时, 数据先从 socket 拷贝到内核空间, 然后再从内核空间拷贝到用户空间

(1)阻塞

阻塞IO, 就是指当调用读取数据的函数（比如 read），这个函数不立马返回结果，而是阻塞当前进程，直到数据被复制到用户进程空间或者是超时出错才解除阻塞，并返回结果。
缺点： 几乎所有的IO接口 ( 包括socket接口 ) 都是阻塞型的。这给 络编程带来了一个很大的问题，如在调用 recv(1024) 的同时，线程将被阻塞，在此期间，线程将无法执行任何运算或响应任何的 络请求。

(2)非阻塞

在非阻塞 IO 中，用户在调用 read 方法后，进程没有被阻塞。内核会立马返回数据给进程，这个数据可能是error提示，也可能是最终的结果。如果要得到最终的结果，就需要用户进程主动的多次调用 read 方法。
缺点： 轮询调用 read 是很费CPU资源的

(3)IO多路复用(select，poll，epoll)

IO 多路复用的好处就在于单个进程就可以同时处理多个 络连接的IO。它的基本原理就是不再由应用程序自己监视连接，取而代之由内核替应用程序监视文件描述符。

• 与传统的多线程/多进程模型比，I/O多路复用的最大优势是系统开销小，系统不需要创建新的额外进程或者线程，也不需要维护这些进程和线程的运行，降底了系统的维护工作量，通过减少无效的系统调用，减少了对 CPU 资源的消耗。
• 适用高并发服务应用开发、一个进程/线程响应多个请求

(4)信 驱动(SIGIO)

信 驱动式IO就是指进程预先告知内核、向内核注册一个信 处理函数、然后用户进程返回不阻塞、当内核数据就绪时会发送一个信 给进程、用户进程便在信 处理函数中调用IO读取数据. 实际IO内核拷贝到用户进程的过程还是阻塞的、信 驱动式IO并没有实现真正的异步、因为通知到进程之后、依然是由进程来完成IO操作

• 在信 驱动式IO模型中、依然不符合POSIX描述的异步IO、只能算是半异步、并且实际中并不常用、
• 回调机制、实现、开发应用难度大

(5)异步IO(POSIX的aio_函数和lio函数)

工作机制是：告知内核启动某个操作、并让内核在整个操作完成后通知我们、这种模型与信 驱动的IO区别在于、信 驱动IO是由内核通知我们何时可以启动一个IO操作, IO操作由用户自定义的信 函数来实现; 而异步IO模型是由内核告知我们IO操作何时完成.

• 异步IO真正实现了POSIX描述的异步IO、是五种IO模型中唯一的异步模型

阻塞IO和非阻塞IO的区别在哪/p>

阻塞IO会一直阻塞住对应的进程直到操作完成、而非阻塞IO在内核还没准备数据的情况下会立刻返回, 阻塞和非阻塞关注的是进程在等待调用结果时的状态、阻塞是指调用结果返回之前、当前进程会被挂起、调用进程只有在得到结果才会返回; 非阻塞调用指不能立刻得到结果、该调用不会阻塞当前进程、

同步IO和异步IO区别在哪/p>

同异步IO的根本区别在于、同步IO主动的调用recvfrom来将数据拷贝到用户内存、而异步则完全不同、它就像是用户进程将整个IO操作交给了他人（内核）完成、然后他人做完后发信 通知、在此期间、用户进程不需要去检查IO操作的状态、也不需要主动的去拷贝数据

信 驱动式IO和异步IO的区别/p>

信 驱动IO与异步IO的区别在于启用异步IO意味着通知内核启动某个IO操作、并让内核在整个操作（包括数据从内核复制到用户缓冲区）完成时通知我们、也就是说、异步IO是由内核通知我们IO操作何时完成、即实际的IO操作也是异步的、信 驱动IO是由内核通知我们何时可以启动一个IO操作、这个IO操作由用户自定义的信 函数来实现

Java中的三种IO模型:

BIO: 同步阻塞IO,应用程序发起read调用后，会一直阻塞，直到在内核把数据拷贝到用户空间中。数据的读取写?必须阻塞在?个线程内等待其完成
NIO: JDK1.4 中引入，对应 java.nio 包，提供了, ，等抽象。NIO 中的 N 可以理解为 Non-blocking，不单纯是 New。它支持面向缓冲的，基于通道的 I/O 操作方法。 对于高负载、高并发的（ 络）应用，应使用 NIO 。Java 中的 NIO 可以看作是 I/O 多路复用模型。
AIO: JDK7 中引?了 NIO 的改进版 NIO 2,它是异步?阻塞的 IO 模型。异步 IO 是基于事件和回调机制实现的，也就是应?操作之后会直接返回，不会堵塞在那?，当后台处理完成，操作系统会通知相应的线程进?后续的操作。AIO 是异步 IO 的缩写，虽然 NIO 在?络操作中，提供了?阻塞的?法，但是 NIO 的 IO ?为还是同步的。

4.进程通信

参考：Linux进程通信

（1）本地进程

• (1)匿名管道(pipe)：

管道是一个固定大小的缓冲区，在Linux中，限制为4KB
特点：
半双工的通信方式；
只能在父子进程能通讯；
速度慢，容量有限

• (2)命名管道(FIFO)：

任何进程间都能通讯，但速度慢；

• (3)消息队列(msgQueue)：

消息队列是链表,具有特定的格式,存放在内存中并由消息队列标识符标识, 其优势是对每个消息指定特定的消息类型，接收的时候不需要按照队列次序，而是可以根据自定义条件接收特定类型的消息。 可以把消息看做一个记录，具有特定的格式以及特定的优先级。
管道和消息队列的通信数据都是先进先出的原则，与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。
消息队列克服了信 承载信息量少，管道只能承载无格式字 节流以及缓冲区大小受限等缺点。
缺点： 容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题；

• (4)共享内存(Shared memory)：

使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信 量等。可以说这是最有用的进程间通信方式。
能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题；

• (5)信 (Signal)：

信 是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生; 信 就是一个内核对象，或者说是一个内核数据结构。只有在父子进程或者是共享内存中，才可以发送字符串消息；
比如：
(1)
(2)

SIGHUP：用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信 的处理是终止进程。
SIGINT：程序终止信 。程序运行过程中，按Ctrl+C键将产生该信 。
SIGQUIT：程序退出信 。程序运行过程中，按Ctrl+键将产生该信 。
SIGBUS和SIGSEGV：进程访问非法地址。
SIGFPE：运算中出现致命错误，如除零操作、数据溢出等。
SIGKILL：用户终止进程执行信 。shell下执行kill -9发送该信 。
SIGTERM：结束进程信 。shell下执行kill 进程pid发送该信 。
SIGALRM：定时器信 。
SIGCLD：子进程退出信 。如果其父进程没有忽略该信 也没有处理该信 ，则子进程退出后将形成僵尸进程。

• (6)信 量(Semaphores)：

信 量是一个计数器，用于多进程对共享数据的访问，信 量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。不能传递复杂消息，只能用来同步。用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

（2）不同机器进程

• 套接字(Socket): (ip地址+端口 )

5.锁和并发

参考：Java中的15中锁

当线程1访问代码块并获取锁对象时，会在java对象头和栈帧中记录偏向的锁的threadID，因为偏向锁不会主动释放锁，因此以后线程1再次获取锁的时候，需要比较当前线程的threadID和Java对象头中的threadID是否一致，如果一致（还是线程1获取锁对象），则无需使用CAS来加锁、解锁；如果不一致（其他线程，如线程2要竞争锁对象，而偏向锁不会主动释放因此还是存储的线程1的threadID），那么需要查看Java对象头中记录的线程1是否存活，如果没有存活，那么锁对象被重置为无锁状态，其它线程（线程2）可以竞争将其设置为偏向锁；如果存活，那么立刻查找该线程（线程1）的栈帧信息，如果还是需要继续持有这个锁对象，那么暂停当前线程1，撤销偏向锁，升级为轻量级锁，如果线程1 不再使用该锁对象，那么将锁对象状态设为无锁状态，重新偏向新的线程。

2. 轻量级锁什么时候升级为重量级锁/li>

线程1获取轻量级锁时会先把锁对象的对象头MarkWord复制一份到线程1的栈帧中创建的用于存储锁记录的空间（称为DisplacedMarkWord），然后使用CAS把对象头中的内容替换为线程1存储的锁记录（DisplacedMarkWord）的地址；
如果在线程1复制对象头的同时（在线程1CAS之前），线程2也准备获取锁，复制了对象头到线程2的锁记录空间中，但是在线程2CAS的时候，发现线程1已经把对象头换了，线程2的CAS失败，那么线程2就尝试使用自旋锁来等待线程1释放锁。
但是如果自旋的时间太长也不行，因为自旋是要消耗CPU的，因此自旋的次数是有限制的，比如10次或者100次，如果自旋次数到了线程1还没有释放锁，或者线程1还在执行，线程2还在自旋等待，这时又有一个线程3过来竞争这个锁对象，那么这个时候轻量级锁就会膨胀为重量级锁。重量级锁把除了拥有锁的线程都阻塞，防止CPU空转。

• 锁粗化

按理来说，同步块的作用范围应该尽可能小，仅在共享数据的实际作用域中才进行同步，这样做的目的是为了使需要同步的操作数量尽可能缩小，缩短阻塞时间，如果存在锁竞争，那么等待锁的线程也能尽快拿到锁。
但是加锁解锁也需要消耗资源，如果存在一系列的连续加锁解锁操作，可能会导致不必要的性能损耗。
锁粗化就是将多个连续的加锁、解锁操作连接在一起，扩展成一个范围更大的锁，避免频繁的加锁解锁操作。

• 锁消除

Java虚拟机在JIT编译时(可以简单理解为当某段代码即将第一次被执行时进行编译，又称即时编译)，通过对运行上下文的扫描，经过逃逸分析，去除不可能存在共享资源竞争的锁，通过这种方式消除没有必要的锁，可以节省毫无意义的请求锁时间

(4)CAS

是一种非阻塞的轻量级的乐观锁，非阻塞式是指一个线程的失败或者挂起不应该影响其他线程的失败或挂起的算法。
CAS(compare and swap),比较并交换。可以解决多线程并行情况下使用锁造成性能损耗的一种机制.CAS 操作包含三个操作数—内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。一个线程从主内存中得到num值，并对num进行操作，写入值的时候，线程会把第一次取到的num值和主内存中num值进行比较，如果相等，就会将改变后的num写入主内存，如果不相等，则一直循环对比，知道成功为止。
优点： 解决变量原子性问题
缺点： 带来ABA问题；CPU开销较大；CAS机制所保证的只是一个变量的原子性操作，而不能保证整个代码块的原子性；
解决：通过版本 解决，每次执行数据的修改操作时都会带上一个版本 ，在预期版本 和内存中版本 相同时，执行修改操作，并对版本 +1，否则不操作。因为版本 是递增的，所以不会出现ABA问题。例：java原子类中的和。

6.JVM内存空间

7.垃圾收集器有哪些

1.1 新生代

新生代采用复制算法，主要的垃圾收集器有三个，Serial、Parallel New 和 Parallel Scavenge，特性如下：

• Serial:单线程收集器，串行方式运行，GC 进行时，其他线程都会停止工作。在单核 CPU 下，收集效率最高。
• Parallel New：Serial 的多线程版本，新生代默认收集器。在多核 CPU 下，效率更高，可以跟CMS收集器配合使用。
• Parallel Scavenge：多线程收集器，更加注重吞吐量，适合交互少的任务，不能跟 CMS 配合使用。

1.2 老年代

• Serial Old：采用标记-整理(压缩)算法，单线程收集。
• Parallel Old：采用标记-整理(压缩)算法，可以跟 Parallel Scavenge 配合使用
• CMS：Concurrent Mark Sweep，采用标记-清除算法，收集线程可以跟用户线程一起工作。
  CMS缺点：吞吐量低、无法处理浮动垃圾、标记清除算法会产生大量内存碎片、并发模式失败后会切到Serial old。

1.3 整堆回收

G1：把堆划分成多个大小相等的Region，新生代和老年代不再物理隔离，多核 CPU 和大内存的场景下有很好的性能。新生代使用复制算法，老年代使用标记-压缩(整理)算法。主要用于多处理器、大内存的场景，它有五个属性：分代、增量、并行(大多时候可以并发)、stop the word、标记整理。

8.跳表和二叉树

跳跃表、红黑树、B+树、AVL树特性比较

(1)AVL树：

适合查找，对插入删除不频繁的场景，利用其高度平衡的特性，AVL还是优于红黑的
高度平衡，有稳定的logn的高度，因此有很好的查找性能O(logn)

(2)红黑树:

平衡二叉树,适合查找，它不要求绝对平衡，所以他的查找性能略逊于AVL，但是它却因此可以获得较好的插入删除性能O(logn)
应用：
（1）epoll在内核中的实现，用红黑树管理事件块
（2）C++的STL中。map和set都是用红黑树实现的
（3）nginx中，用红黑树管理timer等
（4）Java的TreeMap实现
（5）linux进程调度用红黑树管理进程控制块

(3)B+树

更加稳定，数据全部存储在叶子节点, 查询时间复杂度固定为 O(log n)
应用：
主要用在文件系统以及数据库中做索引（MySQL的innodb引擎B+树索引）等，B+树的叶子节点的数据都是使用链表连接起来的，更适合范围查询

(4)跳跃表：

查询、插入、删除有log(n)的复杂的, 空间代价较大。跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性
应用：
redis的有序集合sortset实现

红黑树和跳跃表比较：
对并发和性能有要求的情况下，如何选择合适的数据结构（这里是跳跃表和红黑树）/p>

（1）如果单纯比较性能，跳跃表和红黑树可以说相差不大，但是加上并发的环境就不一样了，
（2）如果要更新数据，跳跃表需要更新的部分就比较少，锁的东西也就比较少，所以不同线程争锁的代价就相对少了，而红黑树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。性能也就不如前者了。
（3）在并发环境下skiplist有另外一个优势，红黑树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，而skiplist的操作显然更加局部性一些，锁需要盯住的节点更少，因此在这样的情况下性能好一些。

为什么 MongoDB 索引选择B-树，而 Mysql 索引选择B+树/p>

（1）MongoDB 是文档型的数据库，是一种 nosql，它使用类 Json 格式保存数据, 性能要求高，B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)，尽可能少的磁盘 IO 是提高性能的有效手段。MongoDB 是聚合型数据库，而 B-树恰好 key 和 data 域聚合在一起。
（2）B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。B+树的查询效率更加稳定，数据全部存储在叶子节点，查询时间复杂度固定为 O(log n)。
（3）B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确

9.分布式

ACID 是数据库事务完整性的理论，CAP 是分布式系统设计理论，BASE 是 CAP 理论中 AP 方案的延伸。

理论

1. CAP理论/h4>

CAP 理论中分区容错性 P 是一定要满足的，在此基础上只能满足可用性 A 或者一致性 C。因此，分布式系统理论上不可能选择 CA 架构，只能选择 CP 或者 AP 架构。 比如 ZooKeeper、HBase 就是 CP 架构，Cassandra、Eureka 就是 AP 架构，Nacos 不仅支持 CP 架构也支持 AP 架构。为啥不可能选择 CA 架构呢举个例子：若系统出现“分区”，系统中的某个节点在进行写操作。为了保证 C， 必须要禁止其他节点的读写操作，这就和 A 发生冲突了。如果为了保证 A，其他节点的读写操作正常的话，那就和 C 发生冲突了。选择 CP 还是 AP 的关键在于当前的业务场景，没有定论，比如对于需要确保强一致性的

                                                        
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！