阿Q技术站

深浅色

美团中间件C++一面 ​

来源：https://www.nowcoder.com/discuss/471814313536147456

计算机网络 ​

1、TCP和UDP 的区别？ ​

1. 连接方式 ​

  • TCP：面向连接（connection-oriented）的协议，在传输数据之前，需要通过三次握手建立连接，传输完成后通过四次挥手释放连接。它提供了可靠的数据传输。
  • UDP：无连接（connectionless）的协议，不需要建立连接，数据可以直接发送。这意味着 UDP 数据传输前没有握手过程，数据报文会直接发往目的地。

2. 可靠性 ​

  • TCP：提供可靠的数据传输。通过序号、确认应答（ACK）、超时重传机制、校验和等手段，保证数据完整性和顺序性，即数据不会丢失、重复或者乱序。
  • UDP：不保证可靠性。UDP 发送数据后，不会等待接收方的确认，丢包、重复、乱序等问题可能发生。它不提供任何纠错和重传机制。

3. 数据传输方式 ​

  • TCP：基于字节流传输。数据在发送方和接收方之间会作为连续的字节流传递，TCP 会将数据分片并按顺序传递给接收方，再重新组装成原始数据流。
  • UDP：基于报文传输。数据以独立的报文（datagram）形式发送，每个报文是一个独立的实体，互相之间没有关系。UDP 保留了数据的报文边界，适合发送少量的、独立的数据包。

4. 流量控制与拥塞控制 ​

  • TCP：提供流量控制（flow control）和拥塞控制（congestion control）机制。TCP 会根据网络状况动态调整发送数据的速率，防止网络拥塞，同时根据接收方的能力调整数据传输速度，避免数据被丢弃。
  • UDP：没有流量控制和拥塞控制。UDP 不关心网络的负载情况，尽可能快地发送数据，因此在网络拥塞时，UDP 可能会导致数据丢失。

5. 速度 ​

  • TCP：由于需要建立连接、确认应答、重传等机制，TCP 的传输速度相对较慢，尤其是在高延迟和高丢包率的网络中，重传可能会进一步降低速度。
  • UDP：速度较快，因为它不需要建立连接，也不需要确认和重传机制，数据传输的延迟较低。适用于对速度要求较高、对数据可靠性要求不高的场景。

6. 首部开销 ​

  • TCP：TCP 首部的开销较大，通常为 20 字节到 60 字节，包含了序列号、确认号、窗口大小、校验和等字段，这些字段用来保证连接的可靠性。
  • UDP：UDP 首部开销较小，固定为 8 字节，包含源端口、目的端口、长度和校验和四个字段。

7. 应用场景 ​

  • TCP：适合对数据传输可靠性要求高的场景，如：
    • 文件传输（FTP）
    • 电子邮件（SMTP）
    • 万维网浏览（HTTP/HTTPS）
    • 数据库查询（SQL）
  • UDP：适合对传输速度要求高、对数据丢失不敏感的场景，如：
    • 视频会议、实时音频和视频流（VoIP、视频流媒体）
    • 在线游戏
    • DNS 查询
    • 广播或多播通信

8. 对比表 ​

特性TCPUDP
连接方式面向连接无连接
可靠性提供可靠传输（有确认和重传）不可靠传输（无确认和重传）
传输方式字节流数据报（报文）
流量控制与拥塞控制有无
速度相对较慢快速
首部开销较大（20-60 字节）较小（8 字节）
典型应用场景文件传输、网页浏览视频会议、实时流、在线游戏

2、服务端处于close wait是什么情况，是由什么造成的？ ​

服务端处于 CLOSE_WAIT 状态，表示服务端的套接字（socket）已经接收到了客户端发来的关闭请求（FIN 报文），并向客户端返回了确认（ACK 报文），但服务端还没有完全关闭连接。这种情况通常发生在服务端收到了关闭请求后，还没有及时执行关闭操作。

CLOSE_WAIT 状态的形成过程： ​

  1. 客户端发起关闭请求（FIN）：客户端主动关闭连接，发送 FIN 报文给服务端。
  2. 服务端接收到 FIN，进入 CLOSE_WAIT 状态：服务端收到客户端的 FIN 报文后，向客户端发送一个 ACK 报文，确认收到了关闭请求。此时，服务端的状态变为 CLOSE_WAIT。
  3. 等待服务端关闭连接：服务端的应用程序此时应该执行关闭操作（通常调用 close() 函数），发送 FIN 报文给客户端，并完成整个连接的关闭过程。

CLOSE_WAIT 状态产生的原因： ​

服务端进入 CLOSE_WAIT 状态的原因主要是服务端没有及时关闭连接，具体常见的原因包括：

  1. 服务端没有调用 close()：应用程序接收到了关闭请求，但因为某些原因，没有及时调用关闭操作（例如代码缺陷、资源处理不当），导致连接一直处于 CLOSE_WAIT 状态。
  2. 资源泄漏或代码缺陷：在某些情况下，服务端应用程序可能存在资源泄漏，导致连接得不到正确处理和释放。常见的情况是忘记处理套接字的关闭，或者误用了文件句柄，导致连接长时间停留在 CLOSE_WAIT 状态。
  3. 服务端业务逻辑复杂：在某些复杂的业务场景下，服务端可能在收到关闭请求时还在处理剩余的任务或等待完成某些操作，导致关闭连接的操作被推迟。

如何解决 CLOSE_WAIT 问题： ​

  1. 检查服务端代码：确保在处理完连接相关操作后，正确调用 close() 或类似的关闭函数来释放连接。
  2. 资源管理：检查是否存在未处理的资源泄漏问题，确保每个打开的套接字都被正确关闭。
  3. 监控和调试：
    • 使用工具（如 netstat、ss 或 lsof）监控系统中的连接状态，查看哪些连接长时间处于 CLOSE_WAIT 状态。
    • 使用代码调试工具分析程序中是否存在长时间未释放连接的情况。
  4. 优化服务端逻辑：如果是业务逻辑问题导致的连接未及时关闭，优化服务端代码逻辑，确保在完成必要的处理后，及时关闭连接。

3、讲讲三次握手和四次挥手？ ​

三次挥手 ​

三次握手

在建立连接之前，Client处于CLOSED状态，而Server处于LISTEN的状态。

  1. 第一次握手：客户端主动给服务端发送一个SYN报文，并携带自己的初始化序列号一起发送给服务端。此时客户端处于一个SYN_SEND的状态。
  2. 第二次握手：服务端收到客户端发来的SYN报文之后，就会以自己的SYN报文作为应答，然后将自己的初始化序列号发送给客户端，并且会将客户端的初始化序列号+1作为自己的ACK值发送给客户端，以表示自己已经收到了客户端的SYN报文。此时服务端处于一个SYN_RECV的状态。
  3. 第三次握手：客户端收到服务端发来的SYN报文之后，会把服务端的初始化序列号+1作为ACK值发送给服务端，用来表示自己已经收到了服务端发来的SYN报文。此时客户端处于一个ESTABLISHED的状态。

四次挥手 ​

四次挥手

  1. 第一次挥手（FIN-1）：
    • 客户端发送一个 FIN 报文段给服务器，表示客户端已经没有数据要发送了，请求关闭连接。
    • 客户端进入 FIN_WAIT_1 状态，等待服务器的确认。
  2. 第二次挥手（ACK）：
    • 服务器收到客户端的 FIN 报文段后，发送一个 ACK 报文段作为应答，表示已经接收到了客户端的关闭请求。
    • 服务器进入 CLOSE_WAIT 状态，等待自己的数据发送完毕。
  3. 第三次挥手（FIN-2）：
    • 服务器发送一个 FIN 报文段给客户端，表示服务器也没有数据要发送了，请求关闭连接。
    • 服务器进入 LAST_ACK 状态，等待客户端的确认。
  4. 第四次挥手（ACK）：
    • 客户端收到服务器的 FIN 报文段后，发送一个 ACK 报文段作为应答，表示已经接收到了服务器的关闭请求。
    • 客户端进入 TIME_WAIT 状态，等待可能出现的延迟数据。
    • 服务器收到客户端的 ACK 报文段后，完成关闭，进入 CLOSED 状态。
    • 客户端在 TIME_WAIT 状态结束后，关闭连接，进入 CLOSED 状态。

4、讲讲慢启动？ ​

目的：用来探测网络的负载或者承受能力。

算法思路：由小到大逐渐增大拥塞窗口，当自己主机刚连进网络时如果一下注入太多资源可能造成网络拥塞，因此循序渐进的探测网络的拥塞程度。每收到一个确认报文拥塞窗口就增加一个报文段。

慢启动

发送方每接收到一个确认报文就将拥塞窗口增加一个报文段。如图所示我们可以看出发送一个收到一个确认下次发两个，收到两个确认下次发2+2=4个收到4个确认下次发4+4等于8个由此可见慢启动算法并不慢。

慢启动门限ssthresh(状态变量)防止拥塞窗口cwnd增长过大引起网络拥塞。

  • 当cwnd<ssthresh，使用慢启动算法。
  • 当cwnd>sshresh，停止使用慢启动算法而使用拥塞避免方法。
  • 当cwnd = sshresh时既可以使用慢启动算法也可以使用拥塞避免算法。

拥塞避免算法：每经过一个RTT，cwnd = cwnd + 1，他的增长是线性的。

当出现网络拥塞时,ssthresh = max(cwnd/2,2)；cwnd = 1；执行慢启动算法。

目的：迅速减少网络中的分组数，有利于路由器将积压的分组处理完。

5、ARP是哪层？ ​

ARP（Address Resolution Protocol，地址解析协议）属于 链路层（OSI 模型的第二层）。虽然 ARP 处理的是 IP 地址与 MAC 地址之间的映射，而 IP 地址是属于网络层的内容，但由于 ARP 主要用于在局域网中将网络层的 IP 地址解析为数据链路层的 MAC 地址，因此它被归类为链路层协议。

ARP 的作用 ​

ARP 的主要作用是在一个局域网内，通过已知的 IP 地址 查找对应的 MAC 地址，从而在网络中进行数据帧的传输。局域网中的数据包传输依赖于 MAC 地址，而 IP 地址则用于网络层的寻址，ARP 负责在这两者之间进行转换。

简单流程 ​

  1. 主机 A 需要向主机 B 发送数据，主机 A 只知道主机 B 的 IP 地址。
  2. 主机 A 在局域网中广播一个 ARP 请求，询问谁拥有这个 IP 地址。
  3. 主机 B 收到 ARP 请求后，返回自己的 MAC 地址给主机 A。
  4. 主机 A 使用主机 B 的 MAC 地址将数据帧传输给主机 B。

6、TCP和UDP是哪层的？ ​

传输层（这我不想再多解释了。。。）

操作系统 ​

1、分页置换算法你知道有啥？ ​

1. FIFO（First-In, First-Out）算法： ​

  • 描述：最简单的一种算法，选择最早加载到内存的页面进行置换。
  • 优点：容易实现，简单直观。
  • 缺点：无法考虑页面的使用频率，可能会淘汰仍然需要的页面，导致“Belady’s Anomaly”（页面错误率增加）。

2. LRU（Least Recently Used）算法： ​

  • 描述：选择最近最久未使用的页面进行置换。假设最近没使用的页面在未来也不大可能马上被访问。
  • 优点：能够较好地反映页面的实际使用情况，性能优于 FIFO。
  • 缺点：实现复杂，需要维护每个页面的使用时间或顺序，开销较大。

3. OPT（Optimal Page Replacement）算法： ​

  • 描述：理论上的最优算法，选择将来最长时间不会被访问的页面进行置换。
  • 优点：可以保证最小的页面错误率，是一种理想算法。
  • 缺点：无法在实际系统中实现，因为无法预知未来的页面访问情况，通常作为评估其他算法性能的标准。

4. Clock（时钟）算法（或 Second-Chance 算法）： ​

  • 描述：这是对 FIFO 的改进版，给每个页面分配一个“使用位”（或“访问位”）。时钟算法类似于一个循环队列，逐一检查页面的使用位，若使用位为 0，置换该页面；若使用位为 1，将其清零并跳过，继续检查下一个页面。
  • 优点：减少了频繁访问的页面被置换的几率，开销较低，接近 LRU 的效果。
  • 缺点：性能不如 LRU，可能需要多次遍历。

5. LFU（Least Frequently Used）算法： ​

  • 描述：选择使用次数最少的页面进行置换。认为使用频率低的页面以后也不大可能被使用。
  • 优点：适合那些历史使用频率可以有效预测未来使用的情况。
  • 缺点：对不久前频繁使用过但之后可能不再使用的页面，无法有效处理，可能会导致次优表现。

6. NRU（Not Recently Used）算法： ​

  • 描述：为每个页面设置两个标志位：一个是是否被访问过，另一个是是否被修改过。定期清除访问位，分为四类页面：未被访问未被修改，未被访问被修改，被访问未被修改，被访问且被修改。根据优先级选择页面替换，优先淘汰未被访问且未被修改的页面。
  • 优点：比 FIFO 更优，考虑了页面的使用情况。
  • 缺点：准确度不如 LRU 等算法。

7. MFU（Most Frequently Used）算法： ​

  • 描述：与 LFU 相反，选择使用次数最多的页面进行置换，基于一种假设：最频繁使用的页面可能是最近刚被分配的，因此其频率较高。
  • 优点：适用于某些特定的工作负载。
  • 缺点：通常效果不如 LFU 或 LRU。

2、听说过page cache吗？ ​

Page Cache（页面缓存） 是操作系统中的一种用于优化文件系统性能的机制。它通过将文件的数据缓存到内存中，减少对磁盘的直接访问，提高读写速度。Page Cache 在现代操作系统（如 Linux、Windows）中广泛使用，用于缓存文件系统中的页面，提升文件 I/O 性能。

工作原理： ​

  • 缓存文件内容：当应用程序从文件中读取数据时，操作系统会将这些数据存储到 Page Cache 中。下次读取相同的数据时，操作系统可以直接从内存中的 Page Cache 提供数据，而无需访问磁盘，减少 I/O 操作的延迟。
  • 写入时缓存：对于写操作，操作系统通常不会立即将数据写入磁盘，而是先将数据写入 Page Cache。Page Cache 中的数据会在适当的时机（如内存压力大或文件关闭时）通过刷回机制写入磁盘，确保数据持久性。这种机制被称为 write-back 策略。
  • 内存管理与回收：Page Cache 会占用系统内存，如果内存不足，操作系统会根据需求淘汰部分缓存页面，释放内存用于其他用途。

优点： ​

  1. 减少磁盘 I/O：通过缓存文件数据，可以大大减少对磁盘的访问，提升文件读写性能。
  2. 提高系统性能：由于内存的访问速度远快于磁盘，Page Cache 能显著减少文件操作的延迟。
  3. Write-back 提高效率：对于写操作，Page Cache 可以减少频繁的磁盘写操作，等到适合的时机再批量写入，优化了写入性能。

运作过程： ​

  1. 读操作：
    • 当文件被读取时，操作系统首先会检查 Page Cache 是否已有相应数据。如果缓存命中，直接从 Page Cache 中返回数据。
    • 如果缓存未命中，则从磁盘加载页面到 Page Cache 中，并将数据返回给请求进程。
  2. 写操作：
    • 写操作也会被暂时存储在 Page Cache 中，数据不会立即写入磁盘。
    • 当内存压力增大或者文件关闭时，操作系统会将这些脏页（已被修改但尚未写回磁盘的页面）刷回磁盘，确保数据的一致性。

Page Cache 和虚拟内存： ​

Page Cache 是虚拟内存管理的一部分。操作系统将文件系统的页面和内存管理结合起来，通过文件映射将文件数据加载到虚拟地址空间。实际上，Page Cache 与应用程序的内存页（如进程的代码、堆栈等）共享相同的物理内存池，因此 Page Cache 的大小会根据系统内存的可用性进行动态调整。

3、我看你写的buffer pool可以将物理页从磁盘拿过来，你是怎么拿过来的，刷盘吗？ ​

数据结构 ​

1、满二叉树有多少个点 ？ ​

对于一个有 深度为 d 的满二叉树，它的节点总数为：n = 2^d - 1

解释： ​

  • 满二叉树 是指每一层的节点数都达到最大值的二叉树（除了叶子节点外，每个节点都有两个子节点）。
  • 深度 d 指的是树的层数，从根节点开始计数，第 1 层为 1，依次往下。
  • 在第 k 层，节点数为 2^{k-1}，因此总节点数是各层节点数的总和：

n = 2^0 + 2^1 + 2^2 + .... + 2^{d-1}

这是一个等比数列，求和公式为：

n = 2^d - 1

例如： ​

对于深度为 3 的满二叉树： n = 2^3 - 1 = 7 该满二叉树有 7 个节点。

2、怎么找链表上的环（快慢指针）？ ​

链表中寻找环可以使用 快慢指针（Floyd 的循环检测算法），这是检测链表是否存在环的一种高效方法，时间复杂度为 O(n)，空间复杂度为 O(1)。

步骤 1：检测是否存在环 ​

  1. 使用两个指针：
    • 慢指针：每次移动一个节点。
    • 快指针：每次移动两个节点。
  2. 如果链表中存在环，快慢指针一定会相遇，因为快指针会最终追上慢指针。
  3. 如果链表没有环，快指针会到达链表末尾（即 nullptr），此时可以确定链表无环。

步骤 2：找到环的起点 ​

  1. 当快慢指针相遇时，说明链表存在环。
  2. 将其中一个指针（比如慢指针）移回链表头，另一个指针保持在相遇点。
  3. 接下来，两指针每次都只移动一个节点，当它们再次相遇时，相遇点就是环的起始位置。

参考代码 ​

c++
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* detectCycle(ListNode* head) {
    if (!head || !head->next) return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    // 检测是否有环
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) { // 快慢指针相遇，说明有环
            // 找到环的起点
            slow = head; // 将慢指针移回到链表头
            while (slow != fast) { // 两指针每次移动一步
                slow = slow->next;
                fast = fast->next;
            }
            return slow; // 相遇点就是环的起点
        }
    }
    
    return nullptr; // 没有环
}

数据库 ​

1、说说为啥用B+树，比较一下红黑树？ ​

为什么使用 B+ 树？ ​

1. 适合大规模数据存储和磁盘访问： ​

B+树的一个关键特性是它将更多的数据存储在少数的节点中，每次磁盘I/O操作读取的内容更大，减少了访问磁盘的次数。特别是在数据库、文件系统等需要频繁进行磁盘读取的场景，B+树的优势非常明显。

2. 高效的范围查询： ​

B+树的叶子节点通过链表连接，这使得范围查询变得非常简单和高效。数据库中很多操作（例如查找某个范围内的数据）都需要进行范围查询，而红黑树由于是二叉树，没有链表连接，范围查询相对较慢。

3. 树的高度更低： ​

B+树的阶数一般可以比较高（即每个节点可以有很多子节点），这使得树的高度很小。高度越小，意味着查找数据时，访问的节点数量越少，尤其是在磁盘访问的情况下，能够显著减少I/O操作的次数。

4. 更稳定的查找时间： ​

B+树的所有数据都存储在叶子节点，查找时所有路径长度相同（从根节点到叶子节点），因此查找时间更加稳定。而红黑树是通过部分平衡的方式实现的，路径长度可能会有一些差异。

B+树和红黑树的区别： ​

1. 树的结构： ​
  • B+树：
    • 是一种多路平衡查找树，每个节点可以有多个子节点。
    • 非叶子节点只存储索引，所有的实际数据都存储在叶子节点上。
    • 叶子节点形成一个链表，方便范围查询。
    • B+树的阶数（degree）决定了每个节点最多能有多少子节点。
  • 红黑树：
    • 是一种二叉平衡查找树，每个节点最多只有两个子节点。
    • 每个节点既存储键，也存储数据。
    • 红黑树通过颜色属性来确保大致的平衡，但不是严格平衡。
2. 节点的分支和深度： ​
  • B+树：
    • 节点的度数很大，可以存储多个关键字，树的高度较小。每个节点指向多个子节点，减少了需要访问的层数。
    • 适合磁盘存储，因为每次从磁盘读入一个节点就能获得大量信息，减少了磁盘I/O操作。
  • 红黑树：
    • 是二叉树，每个节点只存两个子节点，树的高度通常比 B+树高。由于树的高度较大，访问层次更多。
    • 适合存储在内存中，因为内存访问的成本较低，树的深度增加不会显著影响效率。
3. 数据存储方式： ​
  • B+树：
    • 所有实际数据都存储在叶子节点，非叶子节点只作为索引。叶子节点通过链表相连，这样可以方便地进行范围查询。
    • 适合数据库等需要大量磁盘存取的场景，能够很好地利用局部性原理。
  • 红黑树：
    • 数据和键存储在所有节点，适合内存中进行频繁的单点查找。
    • 由于数据直接存储在每个节点上，不适合大规模数据的磁盘访问场景。
4. 查找和范围查询： ​
  • B+树：
    • 由于叶子节点通过链表连接，B+树非常适合进行范围查询，可以从叶子节点直接遍历出有序的数据。
    • B+树的查找性能较为稳定，每次查找都是从根节点到叶子节点，时间复杂度为 O(log⁡n)O(\log n)O(logn)。
  • 红黑树：
    • 红黑树适合单点查找，时间复杂度也是 O(log⁡n)O(\log n)O(logn)。
    • 范围查询相对较慢，因为没有内置的顺序访问机制，需要通过树的中序遍历来实现。
5. 内存和磁盘的适用性： ​
  • B+树：
    • 非常适合存储在磁盘或其他外存中，因为每个节点包含多个元素，可以减少磁盘 I/O 次数。
    • B+树的节点大小可以根据磁盘块的大小进行调整，使得每次访问能够尽量多地读取数据，提升性能。
  • 红黑树：更适合内存中存储，因为内存访问比磁盘快得多，单次访问深度较大的树不会造成显著性能下降。

2、LSM树听说过吗？ ​

LSM树（Log-Structured Merge-tree） 是一种用于高效写入和查询的树型数据结构，特别适用于需要大量写操作的场景，比如日志系统、数据库和文件系统。LSM树主要用于优化写入性能，同时在读取时提供良好的查询能力。

工作原理 ​

LSM树的主要思想是将写操作批量化，并延迟写入磁盘，从而提高写入效率。它通过将数据分布到不同的存储层来实现高效的写入和读取。

  1. 写入操作（MemTable）：当数据写入 LSM 树时，首先会写入到内存中的一个数据结构，通常是一个跳表或平衡二叉搜索树，称为 MemTable。MemTable 是一个内存中树结构的实现，提供了快速的插入和查找操作。

  2. 数据刷新（SSTable）：当 MemTable 达到一定的大小时，它会被转换为一个不可变的数据结构，称为 Immutable MemTable。此时，MemTable 被写入到磁盘中，生成一个 SSTable（Sorted String Table） 文件。SSTable 是一种有序的数据文件，适合于高效的顺序读写。

  3. 合并操作（Merge）：随着时间的推移，多个 SSTable 文件可能会积累在磁盘中。为了保持读取性能，LSM 树会定期执行合并操作，将多个 SSTable 文件合并成更大的 SSTable 文件。这个过程称为 Compaction。

  • 合并操作会将数据重新排序、删除重复或过时的数据，并优化存储结构，以减少后续的查询开销。
  1. 读取操作：在查询数据时，LSM 树首先会查询 MemTable，如果数据不在 MemTable 中，则会在 SSTable 文件中查找。读取操作通常会涉及到多个 SSTable 文件，但合并操作会优化查询路径，使得查询效率较高。

优势 ​

  1. 高效的写入性能：
    • 写操作主要在内存中的 MemTable 进行，内存写入速度快，减少了直接对磁盘的频繁写入。
    • 数据写入磁盘时是批量操作，合并过程也能优化写入效率。
  2. 顺序写入优化：LSM 树的写操作是顺序写入到磁盘上的 SSTable 文件中，这对于现代存储设备（如 SSD）来说是非常高效的，因为顺序写入比随机写入性能更好。
  3. 减少磁盘碎片：合并操作可以减少磁盘碎片，优化存储布局，减少后续的读取开销。
  4. 高效的范围查询：SSTable 文件是有序的，这使得范围查询非常高效，尤其是在合并操作优化之后。

劣势 ​

  1. 读取性能的复杂性：查询操作可能需要遍历多个 SSTable 文件，虽然合并操作能够优化查询路径，但在某些情况下，读取操作可能会比较复杂和耗时。
  2. 合并操作的开销：合并操作是一个资源密集型的过程，可能会影响系统的 I/O 性能和响应时间。

应用场景 ​

  • 数据库系统：如 Apache Cassandra、HBase 和 LevelDB 都使用了 LSM 树来优化写入性能和范围查询能力。
  • 日志系统：适用于需要高效写入和读取日志数据的系统。
  • 文件系统：用于优化文件的写入和读取操作。

3、讲讲mysql 的锁？ ​

1. 行锁（Row Lock） ​

行锁是MySQL的锁粒度最小的一种锁，仅锁定需要操作的具体行。它主要用于InnoDB存储引擎。

特性： ​
  • 锁定具体行：只锁定被操作的行，不会影响其他行。
  • 锁定范围：能够提高并发性能，因为多个事务可以同时操作不同的行而不会发生冲突。
  • 死锁风险：虽然行锁能减少锁竞争，但也可能导致死锁（两个或更多事务互相等待对方持有的锁）。
使用场景： ​
  • 高并发的应用场景，特别是在数据表的并发读取和写入操作中。

2. 表锁（Table Lock） ​

表锁是对整个表加锁。它的粒度较大，但操作简单，不会造成复杂的锁管理。

特性： ​
  • 锁定整个表：锁定整个表，所有对表的操作都被阻塞，直到锁释放。
  • 性能影响：在高并发的环境下，表锁可能会导致性能瓶颈，因为所有的操作都需要等待锁释放。
  • 死锁风险：表锁的死锁风险较低，但锁竞争较高。
使用场景： ​
  • 对表的结构进行操作（如ALTER TABLE），或在低并发环境下进行简单的操作。

3. 意向锁（Intention Lock） ​

意向锁用于协调不同粒度的锁（例如行锁和表锁）之间的冲突。

特性： ​
  • 意向共享锁（IS）：表示事务打算对表中的某些行进行共享锁操作。
  • 意向排它锁（IX）：表示事务打算对表中的某些行进行排它锁操作。
  • 提高效率：避免了事务在进行行锁操作时的冲突，提高了锁的管理效率。
使用场景： ​
  • 在事务中使用行锁时，意向锁帮助协调表级锁和行级锁之间的冲突。

4. 元数据锁（Metadata Lock） ​

元数据锁用于保护对数据库对象的元数据的访问，例如表结构、索引等。

特性： ​
  • 防止并发访问：保护表结构的变化（如ALTER TABLE）不会与其他查询操作冲突。
  • 锁定范围：对表的元数据进行操作时，会自动获取相应的元数据锁，防止在结构操作期间发生其他操作。
使用场景： ​
  • 数据库结构变更或其他涉及到元数据操作的场景。

5. 锁的模式 ​

  • 共享锁（S）：允许事务读取但不能修改数据。
  • 排它锁（X）：允许事务读取和修改数据，其他事务不能对锁定的数据进行任何操作。

4、讲一下innoDB？ ​

它是 MySQL 默认的存储引擎。

1. 特性 ​

1.1 事务支持 ​

ACID：InnoDB 支持 ACID 事务（原子性、一致性、隔离性、持久性），确保数据库操作的可靠性。

  • 原子性：事务中的操作要么全部成功，要么全部失败。
  • 一致性：事务开始前和结束后的数据库状态都必须一致。
  • 隔离性：事务之间的操作互相隔离，一个事务的操作对其他事务不可见。
  • 持久性：一旦事务提交，数据的修改是永久性的，即使系统崩溃也不会丢失。
1.2 行级锁定 ​
  • 行锁：InnoDB 使用行级锁定，允许多个事务同时对不同的行进行操作，减少锁争用，提高并发性能。
  • 锁粒度：行锁的粒度较小，能有效提高并发性，减少锁冲突。
1.3 外键支持 ​
  • 外键约束：InnoDB 支持外键约束，能够实现参照完整性，确保数据之间的关系一致性。
  • 级联操作：支持级联更新和级联删除，自动处理数据的关联更新。
1.4 崩溃恢复 ​

事务日志：InnoDB 使用重做日志（Redo Log）和撤销日志（Undo Log）来确保数据的完整性和持久性。

  • 重做日志：记录事务对数据的修改，用于在系统崩溃后恢复数据。
  • 撤销日志：用于回滚未提交的事务，恢复数据到事务开始之前的状态。
1.5 数据存储结构 ​
  • 聚簇索引：InnoDB 使用聚簇索引（Clustered Index），数据按主键顺序存储在数据页中。主键索引的叶子节点包含实际的数据行。
  • 非聚簇索引：非聚簇索引（Secondary Index）存储索引键和对应的主键值，索引的叶子节点包含主键值，而数据行根据主键值从聚簇索引中获取。
1.6 数据压缩 ​
  • 表压缩：InnoDB 支持表和索引的压缩，减少存储空间的占用，提高 I/O 性能。
  • 页压缩：在存储引擎层进行数据压缩，提高磁盘利用率。

2. 存储结构 ​

2.1 表空间（Tablespace） ​
  • 表空间：InnoDB 使用表空间来存储数据和索引。表空间可以是系统表空间、表独立表空间或通用表空间。
    • 系统表空间：包含所有表的元数据、重做日志和撤销日志。
    • 表独立表空间：每个表有自己的表空间文件，便于管理和备份。
    • 通用表空间：可以包含多个表的数据，支持表的共享空间。
2.2 数据页（Data Page） ​
  • 数据页：InnoDB 中的最小存储单位是数据页，每个数据页的大小通常为 16KB。
  • 页类型：包括数据页、索引页、事务日志页等。

3. 锁机制 ​

3.1 行级锁 ​
  • 共享锁（S Lock）：允许事务读取数据，但不允许修改。
  • 排它锁（X Lock）：允许事务读取和修改数据，其他事务不能对该数据进行任何操作。
3.2 意向锁 ​
  • 意向共享锁（IS）：表示事务打算对表中的某些行进行共享锁操作。
  • 意向排它锁（IX）：表示事务打算对表中的某些行进行排它锁操作。
3.3 死锁检测 ​
  • 死锁检测：InnoDB 使用死锁检测算法自动检测和解决死锁问题，通常会回滚一个或多个事务以解开死锁。

4. 事务隔离级别 ​

InnoDB 支持四种事务隔离级别，控制事务间的可见性：

  • 读未提交（READ UNCOMMITTED）：允许读取未提交的数据，可能会发生脏读。
  • 读已提交（READ COMMITTED）：只允许读取已提交的数据，避免脏读，但可能会发生不可重复读。
  • 可重复读（REPEATABLE READ）：在事务开始时，读取的记录在事务结束前不会被修改，避免脏读和不可重复读。
  • 串行化（SERIALIZABLE）：最严格的隔离级别，事务串行执行，避免脏读、不可重复读和幻读，但性能较低。

5. 使用场景 ​

InnoDB 适用于以下场景：

  • 高并发：行级锁和高效的事务处理使其适用于高并发的应用。
  • 事务处理：需要ACID特性的应用，如银行系统和在线交易系统。
  • 外键约束：需要参照完整性和数据关系一致性的应用。

算法 ​

LC 76--最小覆盖子串 ​

思路 ​

  1. 初始化数据结构：
    • 使用两个哈希表：
      • required：记录目标字符串 t 中每个字符及其出现次数。
      • window：记录当前窗口内每个字符及其出现次数。
    • 使用两个指针 left 和 right，表示当前窗口的左右边界。
    • 使用一个变量 formed 来记录当前窗口内满足 t 中所有字符要求的字符个数。
    • 使用 min_len 和 min_window 来记录当前找到的最小窗口的长度和位置。
  2. 滑动窗口：
    • 右边界扩展：不断向右移动 right 指针，扩展窗口，更新窗口的字符信息。
    • 检查窗口：每次扩展窗口后，检查当前窗口是否包含了 t 中的所有字符。
    • 左边界收缩：当窗口包含了所有字符后，尝试缩小窗口（移动 left 指针），以找到更小的符合条件的窗口。
    • 更新最小窗口：在每次有效窗口更新时，记录当前窗口的最小长度和位置。
  3. 返回结果：如果找到的最小窗口的长度仍然是初始值（表示未找到有效窗口），则返回空字符串；否则返回最小窗口的子串。

参考代码 ​

C++ ​
c++
#include <iostream>
#include <unordered_map>
#include <climits>
#include <string>

// 查找包含 t 所有字符的最小子串
std::string minWindow(std::string s, std::string t) {
    // 如果 t 的长度大于 s 的长度，直接返回空字符串
    if (t.length() > s.length()) return "";

    // 哈希表 required 用于记录目标字符串 t 中每个字符的出现次数
    std::unordered_map<char, int> required;
    // 哈希表 window 用于记录当前窗口中每个字符的出现次数
    std::unordered_map<char, int> window;
    
    // 遍历 t，填充 required 哈希表
    for (char c : t) {
        required[c]++;
    }

    int l = 0, r = 0;  // 窗口的左右指针
    int formed = 0;    // 记录当前窗口中满足目标字符要求的字符个数
    int min_len = INT_MAX;  // 记录最小窗口的长度
    int min_l = 0;    // 记录最小窗口的起始位置

    // 扩展窗口
    while (r < s.length()) {
        char c = s[r];  // 当前窗口的右端字符
        window[c]++;    // 增加当前字符的计数

        // 如果当前字符在目标字符串 t 中，并且窗口中的字符数量达到目标字符的数量要求
        if (required.find(c) != required.end() && window[c] == required[c]) {
            formed++;
        }

        // 当窗口包含 t 中所有字符时，尝试缩小窗口
        while (l <= r && formed == required.size()) {
            char left_char = s[l];  // 当前窗口的左端字符

            // 更新最小窗口
            if (r - l + 1 < min_len) {
                min_len = r - l + 1;
                min_l = l;
            }

            // 缩小窗口
            window[left_char]--;  // 减少左端字符的计数
            // 如果左端字符在目标字符串 t 中，并且窗口中的字符数量低于目标字符的数量要求
            if (required.find(left_char) != required.end() && window[left_char] < required[left_char]) {
                formed--;  // 减少满足字符的计数
            }
            l++;  // 移动左指针，缩小窗口
        }

        // 扩展窗口
        r++;  // 移动右指针，扩大窗口
    }

    // 返回最小窗口子串
    if (min_len == INT_MAX) return "";  // 如果没有找到符合条件的子串，返回空字符串
    return s.substr(min_l, min_len);  // 返回最小子串
}

int main() {
    std::string s, t;

    // 输入字符串 s 和 t
    std::cout << "Enter string s: ";
    std::cin >> s;
    std::cout << "Enter string t: ";
    std::cin >> t;

    // 获取最小覆盖子串
    std::string result = minWindow(s, t);

    // 输出结果
    std::cout << "The minimum window substring is: " << result << std::endl;

    return 0;
}