微信⽀付⾯经
https://www.nowcoder.com/discuss/714191?type=post&order=create&pos=&page=1&ncTraceId
=&channel=-1&source_id=search_post_nctrack

算法题

  1. 重排数组使得组成的数字最⼤ ——排序规则
    2. 翻转链表 ——迭代或递归
    3. 两个⽂件，每个⽂件分别储存了20亿条32位整型数字，求出两个⽂件的交集，限制内存为2G ——bitmap
    4. 常⻅的排序算法。有线性复杂度的排序算法吗 ——插入，冒泡，希尔，堆，快排，归并
    基于比较和交换的算法，复杂度下限就是O(nlogn)
    https://www.cnblogs.com/iwiniwin/p/12633644.html

    • 桶排序：准备m个桶，通过hash函数将元素映射到桶中，并对桶中数据快排；稳定O(n) + O(M * (N/M)log2(N/M))
    • 计数排序：桶排序特殊版本，计算每个数有多少数小于该数，稳定；O(n)
    • 基数排序：基数r,趟数d(由最多位的数字决定) ，每轮需要把桶清空; 稳定；O(d*(n+r))

  2. 100亿个数找前1W⼤的数字。(⽤堆来解决这个问题的时间复杂度和空间复杂度)

    topK问题：https://www.jianshu.com/p/bd3fe9a4339f 堆：建堆时间O(MlogM)，整个复杂度O(NlogM) 优化：将数据集分为1000个文件，建立1000个topK，在每10^6中数据找topk， 再两两合并，最终合并为一个topk。 针对topk问题，常用方法为分治+字典树/hash+小顶堆

  3. 输出链表倒数K个节点，需要处理异常情况，链表为1，K为1000这种 —— 双指针
    7. 判断⼦序列 —— 贪心
    8. 合并两个有序链表; ——建立头结点
    9. ⼆维数组中的查找. ——左下到右上
    10. 链表相加 ——reverse后相加即可
    11. ⽆重复字符的最⻓⼦串 ——滑动窗口
    12. ⼀个数组，数组最⻓连续数的⻓度，如{100，32，7,31,33,101}应该输出3，30min做完，O(n)的
    时间复杂度。 ——hash
    13. 如何设计红包分配 14. K组翻转 ——模拟
    15. 快速排序和插⼊排序的平均时间复杂度
    16. 爬楼梯 ——dp优化
    17. LRU ——双向链表（存值）+哈希表（记录对应数在双向链表中的位置）

    注意公共组件的提取： moveToHead: 将已有node插入头部后 removeNode：将已有node从链表中原位置移除 removeTail：删除尾端节点

  4. 排序算法常⽤哪些，各⾃的适⽤场景，然后他给出⼀个场景描述问你选⽤啥算法，为什么？
    19. 快排最坏时间复杂度多少，什么情况下会出现 ——完全有序
    20. 讲讲红⿊树原理

    • 每个节点是红色或者黑色
    • 根节点黑，叶子节点（NULL）为黑色
    • 若某节点为红色，则子节点为黑色
    • 从一个节点到该节点的子孙节点上的所有路径包含相同数目的黑节点。

  5. 螺旋矩阵【lc54】 ——模拟
    22. 和为s的连续正数序列【剑指57】 ——滑动窗口，(l+r)*(l-r+1)/2
    23. 以拉链法实现⼀个哈希表【要求⼿写链表】 ——开链法
    24. 实现⼀个⼤根堆【实现建堆、弹堆顶两个操作】 ——build(从最后一个非叶子节点开始)，调整：从根节点开始 ```cpp template class bigheap { std::vector nums; int size_; void adjust_fromT2B(int i) {

    1. int l = (i << 1) + 1,r = (i<<1) + 2,bigger = i;
    2. if(l < size_ && nums_[l] > nums_[bigger])
    3.     bigger = l;
    4.    if(r < size_ && nums_[r] > nums_[bigger])
    5.     bigger = r;
    6.    if(bigger != i)
    7. {
    8.     swap(nums_[i],nums_[bigger]);
    9. }
    10. adjust(bigger);

    }

    void adjust_fromB2T(int i) {

    1. int fa = ((i - 1)>>1);
    2. if(nums_[i] > nums_[fa])
    3. {
    4.     swap(nums_[i],nums_[fa]);
    5.     adjust_fromB2T(fa);
    6. }

    }

    void heapify() {

    1. for(int i = (size_ >> 1);i >=0;--i)
    2. {
    3.     adjust(i);
    4. }

    } public:

    1. big_heap(std::vector<T> nums)
    2.     :    nums_(nums),
    3.         size_(nums.size())
    4.         {
    5.             heapify();
    6.         }
    7. T take()
    8. {
    9.     assert(size_ > 0);
    10.     --size_;
    11.     T ret = std::move(nums_[0]);
    12.     nums_[0] = std::move(nums_[size_ - 1]);
    13.     adjust_fromT2B(0);
    14. }
    16. void push(T&& val)
    17. {
    18.     nums_.emplace_back(val);
    19.     ++size_;
    20.     adjust_fromB2T(size_ - 1);
    21. }

};

  1. 25. 哈希原理                                                 ——将关键码值映射到表中的一个位置来访问记录，以加快查找的速度。<br />拉链法：数组存链表头指针，每个链表用以解决冲突<br />• 动态规划问题的解决思路⼀般是怎么样的                         ——
  2. > 1. 将问题化为子问题（子问题和原问题类型相似，规模减小），子问题仅求解一次
  3. > 1. 确定状态
  4. > 1. 边界条件，确定初始状态
  5. > 1. 确定状态转移方程
  7. 26. 负载均衡算法（**(加权)轮询法**(配置高的服务端权重大，被分配的概率大)，**(加权)随机法，源地址哈希法**（根据客户端地址hash映射到不同服务器）），**最小连接数**（由积压连接数最小的服务器优先处理）
  8. <a name="bnmGF"></a>
  9. #  C++ 
  10. 1. static关键字作⽤ 
  12. - 在函数内表示静态局部变量
  13. - 函数外全局区表示该标识符仅限在该文件可见
  14. - 在类内，表示静态成员；静态成员为类所属，不依赖对象生成（静态成员变量需要在类外初始化）
  15. - 未初始化的静态变量在运行期初始化为0
  17. a. static修饰的变量什么时候初始化 
  19. - 全局变量、文件域的静态变量、类的成员变量**在main执行之前的初始化**过程中分配内存；由于在main执行前，故线程安全；
  20. - **局部静态变量（一般在函数内），在第一次使用时分配内存并初始化。；非线程安全！**
  22. 2. C++⾥⾯基类派⽣类构造顺序 
  23. > 1. 调用基类构造函数
  24. >    1. 按基类成员变量定义顺序，调用初始化列表
  25. >    1. 调用基类构造函数
  26. > 2. 调用派生类构造 
  27. >    1. 按派生类变量定义顺序，执行初始化列表
  28. >    1. 调用派生类构造函数
  30. 3. Stl的map介绍⼀下        ——底层结构时红黑树，查询效率为O（nlogn）,插入时会调整红黑树，满足一个排序的效果<br />a. 跟unordered_map的差别， ——底层是哈希表，每个键值会通过哈希函数映射到哈希表中的某个位置。【映射值和键值类型可能不同】<br />冲突解决：哈希表中每个位置配置一个桶，当桶中元素数量<8时，通过开链法解决冲突；否则，将该桶内数据构建为红黑树。<br />b. 你经常⽤这两个哪⼀个 <br />       基于场景选择：若对数据的有序性有要求，那么选择红黑树；若仅需要查找数据是否存在，则建议使用哈希表，占用内存低，速度快。<br />动态内存分配会有什么问题 <br />动态内存分配在管理上⾮常容易出错，主要是三个问题 <br />1. 忘记delete，导致没有释放内存，造成内存泄漏。 <br />2. 使⽤已经释放掉的对象。⽐如多个指针指向相同的内存，delete之后，仍使⽤其他指针 <br />3. 同⼀块内存释放两次。也是多个指针指向相同的内存，⼀个delete之后，再delete，可能就会破坏 <br />⾃由空间。 
  32. 4. 怎么避免内存泄漏 
  33. > 由于栈上的内存的分配和回收都是由编译器控制的，所以在栈上是不会发生内存泄露的，只会发生栈溢出（Stack Overflow），也就是分配的空间超过了规定的栈大小。所以讨论的内存泄漏都是基于堆来理解的
  34. > 1. 尽量避免在堆上分配内存，但对于异步操作，若在栈上分配数据不可行。
  35. > 1. 使用智能指针管理资源，或者使用arena管理所有分配的资源
  36. > 1. 使用携程：携程，令单个线程可同时存在多个上下文，并由用户控制在不同的上下文中进行切换。由于每个携程拥有各自独立的栈空间，则在切换时无需释放栈上的内存，而只需切换到另一个栈上，就可以继续做其他事情了。
  37. > 1. 善用RAII：RAII 可以简化的还不仅仅是内存管理，还可以简化对资源的管理，例如 fd，锁，引用计数等等。
  38. > 
  39. > 当我们需要在堆上分配内存时，可同时在栈上分配一个对象，让栈上的对象对资源进行一个封装。当栈上对象超出作用域时，会调用栈上对象的析构函数释放堆上的内存，将栈对象的生命周期和堆资源绑定。
  41. 5. 虚函数实现机制                  ————虚函数指针和虚函数表
  42. 5. 面向对象和面向过程各自优缺点
  43. > 面向过程
  44. > - 性能好，没有实例化对象的开销
  45. > - 没有面向对象，易维护，易复用，易扩展
  46. > 
  47. 面向对象特性：
  48. > - 程序设计的重点在数据而非过程
  49. > - 程序被划分为对象
  50. > - 数据结构为表现对象而实现，函数作为对某个数据对象的操作，与数据结构紧密结合
  51. > - 数据被隐藏起来，仅通过函数访问
  52. > - 新的数据和函数可容易的添加进来
  54. 7. 面向对象特性
  55. > 封装，继承，多态（静态多态：重载；动态多态：虚函数）
  57. 8. =default, =delete
  58. > =default:将该函数声明为默认函数，由编译器实现；可用与构造，析构，赋值构造等;
  59. > 和｛｝区别：可使构造函数trivial，容易阅读
  60. > 如果时trivial的构造，拷贝，析构，编译器可以以更有效率的方式去实现这些函数，比如跳过构造函数调用，直接采用malloc或memcpy去提高性能
  61. > =delete: 禁用，以一种更简洁的方式防止编译器生成我们不想要的特殊函数
  63. 9. cpp从文本文件到可执行文件的过程
  64. > - 预处理：展开头文件，替换宏，删除注释，替换特殊符号__file___,__line__等
  65. > - 编译：词法分析和语法分析，在所有指令都符合语法规则后，生成汇编文件
  66. > - 优化阶段：
  67. >    - 中间代码的优化：删除公共表达式，循环优化，无用赋值
  68. >    - 目标代码生成的优化：寄存器利用，减少内存访问，流水线等等
  69. > - 汇编：生成目标机器代码
  70. >    - 数据段：全局变量和静态变量
  71. >    - 代码段：程序指令，可执行可读，不可写
  72. > - 链接：将有关的目标文件彼此链接，**即将在一个文件中引用的符号同其在另一个文件中的定义链接起来**。使该目标文件成为一个可被OS创建一个进程来执行的文件。
  74. 10. static_cast和dynamic_cast区别
  76. 对于上行转换（派生类指针转换为基类表示），这两者没有区别<br />但对于下行转换（基类指针转换为派生类表示），dynamic_cast会RTTI检测，若转换出错，会返回null,而static_cast则无视。
  78. **在《**[**C++ RTTI机制下的对象内存模型（透彻）**](http://c.biancheng.net/view/vip_2304.html)**》一节中，我们讲到了有虚函数存在时对象的真实内存模型，并且也了解到，每个类都会在内存中保存一份类型信息，编译器会将存在继承关系的类的类型信息使用指针“连接”起来，从而形成一个继承链（Inheri**[**tan**](http://c.biancheng.net/ref/tan.html)**ce Chain），也就是如下图所示的样子：**<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/2728415/1631544639338-766ce1e2-d90c-4da2-b508-98612410bca1.png#clientId=u19ecb69b-06b0-4&from=paste&id=ueb8feccf&margin=%5Bobject%20Object%5D&name=image.png&originHeight=437&originWidth=194&originalType=url&ratio=1&size=24878&status=done&style=none&taskId=u51b05f39-6a53-45ad-8dbd-0df48af911e)
  80. 当使用 dynamic_cast 对指针进行类型转换时，程序会先找到该指针指向的对象，再根据对象找到当前类（指针指向的对象所属的类）的类型信息，并从此节点开始沿着继承链向上遍历，如果找到了要转化的目标类型，那么说明这种转换是安全的，就能够转换成功，如果没有找到要转换的目标类型，那么说明这种转换存在较大的风险，就不能转换。
  82. 11. STL容器有哪些
  83. - 序列类：vector,list,deque,stack,queue
  84. - 关联：set,map,unordered_set,unordered_map,priority_queue,multi_*
  85. <a name="hd6cW"></a>
  86. # 操作系统 
  87. 1. 进程和线程的区别。喜欢⽤多进程还是多线程，什么场景         <br />能使用多线程就用多线程，如果多线程会带来复杂度，那么就用多进程。    <br />2. 死锁知道吗，怎么避免死锁 
  88. > 死锁四个必要条件
  89. > - 互斥                —— 资源可共享使用
  90. > - 请求和保持        —— 资源一次性分配完
  91. > - 不剥夺              —— 当一个进程/线程保持了某些不可剥夺资源时，请求新资源而得不到满足，则释放已有资源
  92. > - 循环等待            —— 顺序资源分配法，首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完
  94. 3. 进程间通信 <br />4. 协程和进程 <br />5. linux你⽤过的命令列举  ——ps,ulimit,bazel,ps,grep,find,cd,chmod,htop,...<br />6. 并发问题可不可以不⽤锁处理     ——可以，原子变量，或者是乐观锁<br />7. ⽆锁编程如何实现             ——将竞争资源避免竞争，thread_local
  96. 8.   线程之间同步方式 ： 全局变量，静态变量，锁，条件变量，原子变量，信号量，信号。
  97. 8. 自旋锁和可重入锁的区别：
  98. > 自旋锁：当前线程不断地在循环体内执行实现，直到循环条件被改变，才进入临界区；通过CAS实现；当线程竞争不激烈时使用
  99. > 可重入锁：即递归锁，外层函数获得锁后，内存函数可继续加锁，加锁次数和解锁次数需相同；可避免死锁；避免使用可重入锁，因查询core dump时不易找到死锁确切位置
  101. 10. 缓存设计思路：LRU
  102. 10. 物理页置换算法;FIFO,LRU,LFU，时钟置换算法（最近最久（时间）未使用）
  103. 10. 同步IO与异步IO
  104. > 当请求被阻塞，就是同步IO，否则异步IO
  106. 13. 线程数和CPU核数N之间的关系：
  107. > 对于IO密集型应用，线程数设置为2N+1
  108. > 对于CPU密集型应用，线程数设置为N+1
  109. > io优化中：线程数=((线程等待时间+线程CPU时间)/线程CPU时间)  * N;
  110. > **线程等待时间所占比例越高，需要越多线程。线程CPU时间所占比例越高，需要越少线程。**
  112. **14.如何估算携程数目**
  113. > **看需求，如果需要保持连接，则一个连接开一个携程**
  114. > **若需要评估性能，可以开固定数量的携程**
  116. 15.零拷贝技术
  117. > `mmap(diskfd, len)`：当你访问一个文件时，该文件被另一个进程截断，会产生SIGBUS，导致coredump
  118. > `ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);`:只能将文件传输到套接字中。
  119. > `splice(int fd_in, loff_t *off_in, int fd_out, loff_t *off_out, size_t len, unsigned int flags);`：在两个文件描述符中移动数据，其中一方必须是管道文件
  120. > 
  122. <a name="xo1RZ"></a>
  123. # 计⽹
  124. 1. Get和post的区别 
  125. > GET：可书签，可缓存，可保留浏览器历史（参数），参数在url中可见
  126. > POST：数据不显示在URL中
  128. 2. http的缓存了解吗 
  129. > 不会
  131. 3. tcp和udp的区别，tcp怎么保证可靠，tcp和udp使⽤场景 
  132. > TCP可靠保证：校验和，序列号，确认应答，流量控制，拥塞控制，超时重传，三次握手
  134. 4. 三次握⼿介绍⼀下，为什么⼀定要三次握⼿，两次握⼿可以吗？ 
  135. > 避免失效的连接重新建立
  137. 5. Accept发⽣在三次握⼿哪⼀步 
  138. > 发生在三次握手完成之后，此时双向连接建立，可调用accept获得次连接
  140. 6. Tcp怎么保证数据包收到 
  141. > ACK+SEQ+重传
  143. 7. TCP是怎么保证它的传输安全的？
  144. >  通过HTTPS或者应用层封装加密协议
  146. 8. 序列号怎么⽣成 
  147. > 在32位机器上，初始序列号由一个32位计数器来设置，每4us加1，并非完全随机
  148. > linux系统的初始序列号生成：
  149. > 1. 为时钟加一个偏移量【该偏移量在4元组基础上，用加密散列函数得到，且加密散列函数5分钟改变一次】
  151. 9. 序列号怎么变化的，随着确认接收 <br />10. 序列号回绕怎么办（这个没回答出来，⽤tcp⾸部补充字段时间戳就⾏了，舍弃最远的时间戳数据 <br />包） 
  152. > TCP回绕：ISN按照一定算法生成，可能很大，故会出现seq回绕到0的情况。由于tcp对于丢包和乱序都是基于seq大小比较，故此时出现TCP回绕问题。、
  153. > 解决:
  154. > 可包容回绕,最大回绕级别是2^(n-1);
  156. ```cpp
  157. static inline bool before(__u32 seq1, __u32 seq2)
  158. {
  159.         return (__s32)(seq1-seq2) < 0;
  160. }
  161. #define after(seq2, seq1)     before(seq1, seq2)
  162. 假设 n = 3 ,[0~7]
  163. (1) seq1 = 1, seq2 = 2;
  164.   001
  165.  -010 -> + 110
  166.   111  负数 -1
  167. (2) seq1 = 7,seq2 =0;
  168.   111
  169.  +000 
  170.   111 负数 -1

  1. 流量控制和拥塞控制区别

    流量控制：端到端的控制，通过滑动窗口实现 拥塞控制：A与B之间的网络拥塞发生丢包，传输过慢等问题，有拥塞窗口实现

  2. TCP中Time-wait是做什么的？HTTP和HTTPS的区别？HTTPS具体过程？HTTPS能否防⽌中间⼈
    攻击

    TIME-WAIT: 2MSL，MSL为一个TCP报文在网络中存活的最大时间，一般为两分钟

    • 允许全双工连接可靠关闭：确保最后一个ACK被服务器接受；若无TIME-WAIT，服务器未收到LASTACK,服务器重传FIN，由于客户端已经关闭，将回复RST响应，服务端将此视为一个错误。
    • 保证网络中旧链接的延迟数据包不会被新链接接收

    image.pngSSL层位于TCP协议和各种应用层协议之间，为数据通信提供安全支持。 中间人攻击：攻击者分别与通信两段建立独立的连接，并交换其所收到的数据，使通讯两段认为他们正在通过一个私密的连接直接通过； HTTPS通过SSL身份认证，可以验证参加通讯的一方或者双方证书是否由CA机构颁发。【证书：”元信息”+密文（由CA私钥加密）】 “元信息” + 证书的hash加密算法 = 摘要A; “密文” + CA证书公钥 = 摘要B; 若攻击者截获服务端发来的证书，并修改其中的元信息，由于攻击者没有CA的私钥，无法对元信息加密生成密文； 故客户端验证2份摘要时，可以判断是否存在中间人攻击；

  3. 说⼀下Http 跟Https
    14. Https⽐Http多了哪些状态码?

    1xx:消息 2xx:成功 200：OK 3xx:重定向 301：资源永久转移 4xx:客户端错误 404: 请求资源不存在 5xx:服务端错误 500：内部服务器错误

  4. Https是怎么保证安全传输的？（Https的加密过程）
    16. 浏览器输⼊Url发⽣了什么？
    17. Http请求包是怎么接收的？
    18. socket编程有了解过吗？没了解，然后撤了⽹络中短链接占⽤太多资源的时候socket可以复⽤
    • TIME_WAIT状态出现在连接哪个阶段 —— 主动关闭 发送LASTACK时出现
    • TIME_WAIT状态连接过多如何解决（起因：高并发短连接时，服务器主动关闭已完成的连接时，会出现大量的TIME-WAIT连接）

    调整内核参数来解决：

    • SYN参数，当SYN队列溢出时，启用cookie来处理
    • 开启TIME-WAIT SOCKET重用
    • 开启TIME-WAIT SOCKET快速回收

• ⻓连接会有什么问题

Nagle算法导致的发送延时问题 Nagle算法之所以可以减少小包的数量，是因为它可以将小包拼接起来发送。

• TCP的滑动窗⼝机制
19.慢开始，拥塞避免，快重传，快恢复（直接执行拥塞避免）

WX支付面经收集 - 图2 快重传：让对方尽快进行重传，而不是等待超时重传计时器超时。 快恢复：收到三次ACK后，执行快恢复算法，即直接进入拥塞避免状态。

20.TCP四种计时器

  • 重传计时器：发送报文段，创建该特定报文段的重传计时器
  • 坚持计时器：收到窗口大小为0的确认，启动坚持计时器【TCP中不会对确认进行确认，故可能会造成死锁】
  • 保活计时器：防止一个TCP连接过长时间空闲
  • 等待计时器：TIME-WAIT,等待2MSL

21.TCP头部
image.png
22.TCP如何分段?IP层如何分片

IP层的分片大小根据链路层MTU确定，一般为1500；IP层不保证超时重传； TCP层根据MSS进行TCP报文的组合，即每个TCP报文＜MSS； 一个TCP链接首次的MSS根据链路MTU来确定（1500 - 20(IP) - 20(TCP)），故TCP分段后，IP肯定不会分片； 但UDP没有MSS限制，分片由IP层负责；

  1. HTTP1.0，HTTP1.1,HTTP2.0区别

    • 1.0和1.1：长连接，解决带宽（1.1支持只发送header信息），新增状态码，如410，请求资源被永久删除
    • 1.1和2.0: 多路复用，头部压缩（1.1状态行和头部不会压缩），2.0采用HPACK算法对header进行压缩

  2. SYN攻击如何处理

    SYN即使DoS攻击，通过发送大量的SYN连接，占用服务器大量资源(TCB)，以使合法用户无法得到服务器响应。 服务端接收到SYN报文，就需要为该请求分配一个TCB，一个TCB至少需要280字节，并返回一个SYN ACK报文，转为SYN-RECEIVED状态；

    • 解决SYN泛洪攻击即解决TCP的分配时机，延缓TCB的分配
      • Syn cache技术：当系统收到一个SYN报文时，维护一个专用的HASH表用于保存这种半连接信息，直到收到正确的ACK报文再分配TCB
      • Syn cookie: 占用资源更少，通过算法生成SeqNum,考虑了对方的信息和己方的信息，再收到对方ACK报文后，重新计算一边，判断是否与对方报文中的Seq相同，从而决定是否分配TCB

  3. HTTP CHUNCK

请求静态内容时，可以通过Content-length消息字段告诉客户端需要接收多少数据，
但请求动态页面时，无法预先知晓内容大小，故此时可使用Transfer-encoding:chunk模式来传输数据。
chunk编码时，消息头部有Transfer-encoding:chunk
编码使用若干个chunk组成，由一个标明长度为0的chunk作为结束
每个chunk由两部分组成，长度和内容。

  1. TCP状态机

image.png

数据库

  1. 说⼀下你知道的mysql索引？

    普通索引 唯一索引 主键索引 联合索引：最左匹配

  2. mysql索引为什么使⽤B+树不使⽤B树 为什么不使⽤红⿊树？

    B树的所有节点都保存数据，这样在叶子节点中保存的索引就会变少，相同数据量下，整个树的高度就会变高，且查询不稳定 红黑树同样的理由

  3. 红⿊树的五个特性记得吗？

    • 根节点为黑色
    • 空叶子节点为黑色
    • 若节点为红色，其子节点为黑色
    • 从一个节点到该节点的子孙节点上的所有路径包含相同数目的黑节点。

  4. mysql事务隔离级别有哪些 RU RC RR SERI
    5. 乐观锁和悲观锁区别，适⽤场景
    乐观锁：假设多用户并发处理时不会互相影响，各事务能在不产生锁的情况下处理各自的数据。在提交数据更新前，每个事务读取数据时，都会检查是否有其他事务修改了该数据，若是，则回滚。
    MVCC:

    隐藏字段：事务ID，回滚指针 READVIEW 该行记录的唯一隐藏主键

适用场景：事务之间的竞争概率小，做出的修改直到提交事务时才去锁定，不会产生任何锁和死锁
悲观锁：主要用于数据争用激烈的环境，锁保护数据的成本远低于回滚的成本
6. MySQL的ACID，隔离级别？解决了什么问题？MVVC⼜解决了什么问题？哪些数据库⽤B+树？

脏读：事务对数据的修改未提交时，相同事务中多次select返回的结果集不同 不可重复读：更新（已提交） 幻读：插入（已提交）

  1. Mysql事务隔离级别，幻读是怎么解决的

    幻读：一个事务内，同一个select在不同时间内执行，得到不同的结果集； Innodb中解决幻读的方式：READ_VIEW,undo log

  2. 如何创建索引，每⼀列都设置为索引为什么不⾏，从哪⼏个⽅⾯考虑

    1. 创建表时设置primary key 或 unique key
    2. 创建表后

    ALTER TABLE students ADD PRIMARY KEY (student_id); ALTER TABLE students MODIFY student_id INT auto_increment;

每行都设置索引问题：

  • 创建索引和维护索引需要时间和空间。
  • 对表进行增删改时，需要维护索引

建立索引需要考虑的问题：

  • 设置主键列，确保唯一性
  • 需要经常在作为筛选条件的列
  • 需要范围搜索的列

9.为何要创建索引

  1. 创建唯一性索引，保证每行数据的唯一性
  2. 加快表的检索速度
  3. 通过索引，可以在查询过程中使用优化隐藏器
  4. 加速表与表之间的连接
  1. 分布式事务：2PC、3PC
    10.为什么mysql底层不用红黑树？
    在数据量非常大的清空下，树的高度很高，查找效率下降。而B+树一个节点可以存储很多索引，每个节点中的索引按序排列，二分查找。所以树的高度可以大大降低
    11.h=3时，page_size=16KB，叶子节点每个索引+数据的大小为1KB,则整个B+树可以存放多少个数据
    1. 每个非叶子节点可存放索引16K/(8+6)=1170个索引
    2. 每个页可存放叶子节点 16K/1K=16
    3. 故总数据量 1170117016=2400w

image.png

  1. 索引的基本原理

索引用来快速寻找哪些具有特定值的记录，若无索引，则需要进行全表扫描
索引的原理就是：将无序的数据转变为有序的查询
一般来说，若不需进行范围查询，可使用hash来创建索引
否则一般通过B+树来创建索引结构

  1. mysql中索引类型对数据库性能的影响
    1. 普通索引：允许索引值重复
    2. 唯一索引：可以保证数据记录的唯一性
    3. 主键索引：特殊的唯一索引，一张表中仅能存在一个，主键用于唯一标识一条记录
    4. 联合索引：索引可以覆盖多个数据列，INDEX(columnA,columnB)
    5. 全文索引：通过建立倒排索引，可以极大提升检索效率，解决判断字段是否包含的问题。是目前搜索引擎使用的一种关键技术。ALTER TABLE tablename ADD FULLTEXT(column)

通过使用索引，在查询时会使用优化隐藏起，可大大提高查询效率，但在增删改时，对于主键索引和唯一索引来说，若其不在buffer pool中，需要从磁盘取出来判断唯一性，其余二级索引则可change buffer的merge技术，来实现提高增删改查的效率。

  • 索引需要占用物理空间存储
  • 若建立聚簇索引（叶子节点包含记录值），需要的空间会更大
  • 若非聚集索引（二级索引）很多，若聚集索引改变，非聚集索引也要进行变更

14.mysql聚簇索引和非聚簇索引的区别
都是使用B+树的数据结构

  • 聚簇索引：索引和记录存放到一起，按一定顺序组织；找到了索引就找到了记录，数据的物理存放顺序和索引一致，相邻索引的数据也是相邻的
    • 优势：可以直接获取数据记录，不用再次间接访问；范围查询效率高，因为数据按索引从小到大排列。；适合于在排序的场合使用。
    • 劣势：
      • 维护索引昂贵：特别是在插入新行或主键被更新导致分页（page split）时。建议负载较低时，使用OPTIMIZE TABLE优化表，因为行数据移动时可能产生碎片
      • 若采用uuid作为主键，使数据存储稀疏(因为分表问题)，就可能出现聚簇索引比全表扫描还慢的情况，建议使用int,auto_increment作为主键
      • 主键较大的情况下，会增加所有非聚集索引的大小；
  • 非聚簇索引：索引和记录分开存放（myisam），叶子节点存储的是索引和数据行地址；即根据索引先拿到行地址，然后再取磁盘查找数据。

Innodb选择主键的顺序：user-defined,unique,row_id；非聚簇索引均为辅助索引，叶子节点存储的是主键值
myisam使用的是非聚簇索引，非聚簇索引不同的树看起来没什么不同，索引树是独立的。
15.索引设计的原则
查询更快，占用空间更小

  • 要
    1. 适合索引的列出现在where子句中或连接子句中
    2. 短索引。若对长字符串列进行索引，应指定一个前缀长度，可大量节省存储空间
    3. 定义有外键列的数据一定要有索引【】
  • 不要
    1. 不要过度索引。索引需要额外磁盘空间，对索引的修改和插入都可能造成索引的重构，索引列越多，重构时间越长
    2. 更新频繁的字段不要创建索引
    3. 对于定义为text,image,bit的数据的列不要创建索引
    4. 基数较小的表不用索引

16.锁的类型有哪些?
基于锁的属性：共享锁，排他锁
基于锁的粒度：行锁，表锁，页锁，记录锁，间隙锁，临键锁
基于锁的状态（表级别）：意向共享锁，意向排他锁

若事务A加锁成功后，就设置一个状态告诉后面的事务，当前表里已经加了一个排他锁，你们不能继续加锁了。后面的事务获取这个状态，就可以了解是否可以加锁，避免了对整个索引树的遍历去查找加锁状态，而这个状态就是意向锁

  • 意向共享锁：当一个事务需要对整个表加共享锁时，需要获得这个表的意向共享锁
  • 意向排他锁：当一个事务需要对整个表加排他锁时，需要获得这个表的意向排他锁
  • 共享锁：读共享；写互斥；支持并发读数据。读时不可修改数据，避免出现重复读
  • 排他锁：读写均互斥。避免出现脏读，幻读，不可重复读
  • 行锁：锁住表的某一行或多行数据；粒度小，加锁简单，冲突小；会造成死锁【比如说两个事务分别持有某个表两个行的锁，然后又互相请求修改对方的行，即造成死锁】
  • 记录锁：行锁的一种，锁住表的某一行记录；精确条件命中，命中的条件字段时唯一索引。
  • 表锁：锁住整个表；粒度大，加锁麻烦，冲突多；
  • 页锁：介于行锁和表锁之间的一种锁；一次锁定相邻的一组记录；开销介于行锁和表锁之间；会出现死锁；
  • 间隙锁：行锁的一种，锁住表记录里某个区间，当相邻表id之间出现空隙则会形成一个区间【左开右闭】
  • 临建锁：行锁的一种，时记录锁和间隙锁的组合；临建锁会把查询出来的记录锁住，同时将改范围查询内的所有间隙锁住，再把下一个区间锁住。
    • 触发条件：范围查询并命中，查询命中了索引
  1. mysql执行计划怎么看？（type）
  2. 事务的基本特性（ACID）和隔离级别

    事务的最终目的是一致性，故事务通过原子性、隔离性和持久性来达成这个目的 一致性简单的来说：比如说对于唯一id的操作，事务处理前是唯一的，事务提交后也是唯一的，这就是一致性

原子性：事务操作要么全部成功要么全部失败
一致性：数据库总是从一个一致性状态转变为另一个一致性状态。比如A转账给B100块，但A只有90块，支付之前数据库里的数据都是符合约束的，但如果事务执行成功了，当前数据库便破坏了约束，因此事务不能成功。这里即事务提供了一致性保证
隔离性：一个事务的修改再最终提交前，其余事务不可见
持久性：事务提交后，所作的修改会永久保存到数据库中。
17.主从同步原理？
image.png
image.png
全同步复制：需要等待10个从节点全部备份完成
半同步复制：假设10个从节点，只要有一个从节点返回ACK，就认为从库备份完成
18.简述Myisam和innodb区别
image.pngimage.png
19. 联合索引的底层结构如何？

image.png
image.png
最左前缀法则，只有红框会使用联合索引

场景

  1. 给微信朋友圈设计一个表的结构来存储，怎么查询某一条朋友圈

    三个表：用户id表，推文表（记录推文，包含User id），好友id列表 表该如何存放数据：hashed by date or userid or pyqid,需要考虑热数据和sharding问题 查询朋友圈一般分为：查询自身朋友圈列表和查询用户朋友圈列表。 对于查询自身朋友圈列表： 需求是查询所有好友user pyq,有如下几种策略：
    1. 直接通过好友id列表query DB，缺点是时间慢，但准确

    1. 通过缓存服务器查询——此时要考虑谁去更新缓存，以及请求次数和请求的量级

  2. 主从Reactor模型

image.png
流程：
Reactor主线程对象监听连接事件，通过acceptor处理
当acceptor处理连接事件后，由主线程将连接分配给从Reactor
从Reactor将连接加入到连接队列监听，并创建handler处理事件（read,write）
当有新事件发生时，从reactor采用对于的handler处理事件。
handler读取数据后，分发给worker线程处理
worker线程池分配独立的worker处理结果
hanlder收到结果后再返回给客户端。

核心：
mainReactor处理连接，读写工作交由subReactor处理，工作线程池只负责处理业务逻辑；
处理读写事件的subreactor个数一般和CPU数量相同，一个subReactor对应一个线程，业务逻辑有线程池处理。

问题：

  • 监听线程分发连接

轮询分发

  • 客户连接的分发

采用无锁队列【需要进行边界分析，由于采用的是有界循环队列，同时对头尾指针进行操作，会没有原子性】

  • 如何处理各IO线程负责不均衡情况

【加权轮询策略进行分发】

  • 如何实现连接的被动分发

【维护一个客户连接池，由IO线程根据自身情况自取】

  • 连接主动分发和连接被动分发的区别

从锁的争用程度和链接的饥饿程度考虑

  • IO线程和工作线程为什么要分离开来

业务逻辑和读写逻辑分离，便于修改和优化。
提高吞吐量。

  • 在数据读写方面如何降低

网卡和磁盘设备与内核缓冲区的数据拷贝通过DMA控制器完成，内核缓冲区与用户态缓冲区的数据拷贝由CPU完成。
可采用零拷贝技术较少用户态内核态切换及拷贝次数，如mmap等