总纲：

1.自我介绍

2.应答与反提问

3.面试引导

介绍一下TCP/IP协议

TCP/IP协议是互联网通信的基础，它是一个由许多协议组成的协议族，用于在网络上传输数据。TCP/IP协议分为四层：应用层、传输层、网络层和数据链路层。

应用层是用户应用程序与TCP/IP协议的接口层，它提供各种服务，如HTTP、FTP、SMTP等。
传输层负责在两台计算机之间建立连接，并保证数据的传输。TCP协议和UDP协议是传输层的两个主要协议，TCP协议提供可靠的传输，UDP协议提供不可靠的传输。
网络层负责在网络中路由数据包，IP协议是网络层的主要协议，它为数据包分配IP地址，并负责在网络中传输数据包。
数据链路层负责在物理链路上传输数据帧，ARP协议和MAC协议是数据链路层的主要协议，MAC协议它为数据帧分配MAC地址，并负责在物理链路上传输数据帧。

TCP/IP协议是一个复杂的协议，它为互联网的通信提供了可靠的基础。

ARP协议

地址解析协议（ARP）是将IP地址解析为MAC地址的协议。IP地址是网络层的地址，MAC地址是数据链路层的地址。当一台计算机要向另一台计算机发送数据时，它必须知道目标计算机的MAC地址。ARP协议就是用来解决这个问题的。

ARP协议的工作原理是：当一台计算机要向另一台计算机发送数据时，它首先会查看自己的ARP缓存。如果目标计算机的MAC地址在ARP缓存中，则计算机会直接使用该MAC地址发送数据。如果目标计算机的MAC地址不在ARP缓存中，则计算机会发送一个ARP请求报文。ARP请求报文会包含发送计算机的IP地址和MAC地址。收到ARP请求报文的计算机会响应一个ARP应答报文。ARP应答报文会包含目标计算机的IP地址和MAC地址。发送计算机收到ARP应答报文后，会将目标计算机的MAC地址保存在自己的ARP缓存中。

ARP协议是一个动态协议，这意味着计算机会不断更新自己的ARP缓存。当计算机不再与某台计算机通信时，它会从ARP缓存中删除该计算机的MAC地址。

MAC地址和IP地址有什么区别

MAC地址和IP地址是计算机或其他网络设备在网络上唯一标识自己的两个地址。MAC地址是物理地址，IP地址是逻辑地址。

  • MAC地址（Media Access Control Address）又称物理地址、硬件地址，由网卡厂商在生产时写入网卡的EEPROM中，是唯一的。MAC地址通常由12位十六进制数字组成，例如00-11-22-33-44-55。
  • IP地址（Internet Protocol Address）是网络层地址，由网络管理员分配。IP地址通常由4位十进制数字组成，例如192.168.1.1。

MAC地址和IP地址的区别如下：

  • MAC地址是唯一的，而IP地址不是唯一的。
  • MAC地址在物理层上使用，而IP地址在网络层上使用。
  • MAC地址用于在同一个局域网内通信，而IP地址用于在不同网络之间通信。

MAC地址和IP地址都是网络通信中必不可少的地址。MAC地址用于在同一个局域网内定位设备，IP地址用于在不同网络之间定位设备。

介绍一下什么是局域网

局域网（LAN）是指在一个相对较小的地理范围内，由多台计算机和其他网络设备通过通信线路连接起来形成的计算机网络；局域网是一个逻辑上的网络，它可以在一个网关下，也可以存在于多个网关之间，这取决于网络的拓扑结构和配置。它通常覆盖一个较小的地理区域，例如家庭、办公室、学校、企业内部等。

局域网中的==IP地址通常都是在一个IP地址段中==。IP地址段是一个范围内的IP地址，例如192.168.1.0/24。IP地址段中的所有IP地址都属于同一个网络。局域网中的设备必须使用同一个IP地址段才能相互通信。

如果局域网中的设备使用不同的IP地址段，则无法相互通信。这时，需要使用路由器来连接两个网络，并将两个网络的IP地址转换成另一个网络的IP地址。

讲一下DNS

DNS（Domain Name System）是一个用于将域名转换为对应IP地址的分布式命名系统。在互联网上，计算机和其他网络设备通常使用IP地址来相互识别和通信。然而，IP地址是一串数字，对于人类来说不太直观和难以记忆。为了解决这个问题，DNS被设计出来，允许我们使用易记的域名来访问网站，而不需要记住复杂的IP地址。

5.DNS协议具体是怎么找到服务器地址的(域名解析的工作流程)

  1. 客户端首先会发出一个 DNS 请求，问 www.server.com 的 IP 是啥，并发给本地 DNS 服务器（也就是客户端的 TCP/IP 设置中填写的 DNS 服务器地址）。
  2. 本地域名服务器收到客户端的请求后，如果缓存里的表格能找到 www.server.com，则它直接返回 IP 地址。如果没有，本地 DNS 会去问它的根域名服务器。
  3. 根域名服务器是最高层次的，它不直接用于域名解析，但能指明去哪个顶级域名服务器寻找。发现后置是 .com，将 .com 顶级域名服务器地址发给本地DNS。
  4. 本地 DNS 向顶级域名服务器发起请求，顶级域名服务器给出 www.server.com 区域的权威 DNS 服务器的地址，它是域名解析结果的原出处。
  5. 权威 DNS 服务器查询后将对应的 IP 地址 X.X.X.X 告诉本地 DNS。本地 DNS 再将 IP 地址返回客户端，客户端和目标建立连接。

介绍一下什么是Socket

套接字（英语：Socket）是计算机网络中进程间通信（IPC）的一种形式，它是一种通信端点。套接字可以用于进程间在网络上通信，也可以用于进程间在同一台计算机上通信。套接字通过IP地址和端口号来唯一标识一个进程。

Socket可以分为两种类型：

  1. TCP Socket：基于传输控制协议（TCP）的Socket。TCP提供可靠的、面向连接的通信。使用TCP Socket时，数据在发送和接收之前必须先建立连接，确保数据按照正确的顺序到达目的地，而且不会丢失或损坏。TCP Socket适用于需要可靠数据传输的场景，如文件传输、Web浏览、数据库访问等。

  2. UDP Socket：基于用户数据报协议（UDP）的Socket。UDP提供不可靠的、无连接的通信。使用UDP Socket时，数据可以直接发送到目标地址，无需建立连接，但不保证数据的可靠性。UDP适用于一些实时性要求较高的应用，如音频/视频传输、游戏等。

详细介绍一下socket通信的过程

  1. 创建一个用于监听的套接字,本质是一个文件描述符；

  2. 将这个监听文件描述符和本地的IP和端口绑定

  3. 设置监听，监听的fd开始工作

  4. 阻塞等待，当有客户端发起连接，解除阻塞，接受客户端的连接，会得到一个和客户端通信的套接字（fd）一个新的fd

  5. 通信：接收数据，发送数据；

    TCP收发数据用函数send()和recv()，或者read()和write();

    UDP收发数据用函数recvfrom()，sendto();

  6. 通信结束，断开连接

==基于UDP的Socket通信过程没有监听步骤，因为UDP提供不可靠的、无连接的通信。==

文件描述符

文件描述符是一个在计算机程序中使用的数字，它用于==标识打开的文件==。文件描述符由操作系统分配，并由程序使用来访问文件。

文件描述符用于访问文件的各种操作，例如读取、写入和关闭文件。程序可以使用文件描述符来读取和写入文件的内容，也可以使用文件描述符来获取文件的属性，例如文件大小和文件类型。

一个端口可以建立多个连接吗

端口与客户端连接

一个端口可以同时建立多个连接，需要用IO多路复技术实现对多个连接管理。尽管服务器的端口号是固定的，但可以同时与多个不同的客户端建立连接，每个连接都会有独立的Socket，用于在客户端和服务器之间进行数据传输。这样服务器可以并发处理多个客户端请求。

当一个服务器端程序需要处理多个客户端连接时，传统的做法是为每个客户端连接创建一个单独的线程或进程来处理通信。每个客户端连接使用的是同一个端口号，但有不同的套接字和线程/进程来处理通信。

IO多路复用

IO多路复用，可以在==一个线程或进程中同时监视多个I/O通道（例如Socket）==，并在这些通道中有数据可读或可写时立即进行相应的处理，而无需阻塞等待。这样一来，一个线程/进程就可以同时管理多个客户端连接，实现高并发处理，而不需要为每个连接创建单独的线程或进程。

IO多路复用与线程池

用IO多路复用来管理多个客户端连接，并使用线程池来处理每个连接的数据交互。具体实现可以是，将IO多路复用作为主循环，用于监视多个客户端连接的可读/可写事件，当有事件发生时，从线程池中获取一个空闲线程，然后将连接的数据处理任务交给这个线程去处理。

线程池技术与传统方法

传统的做法是为每个任务或客户端连接创建一个单独的线程或进程，用于处理任务。这样频繁地创建和销毁线程会带来较大的开销，包括线程的创建、上下文切换和销毁等。

线程池相比传统的处理方法，通过预先创建线程、优化线程的重用、控制线程数量、管理任务队列和提供任务调度等机制，可以更高效地处理并发任务，降低系统开销，提高系统性能和资源利用率。

对webserver项目进行深入的介绍

一个HTTP的报文有哪些内容？

一个HTTP的请求报文主要包括以下内容：

  1. 请求行（Request Line）：请求行包含HTTP请求的方法、目标URL和HTTP协议版本。例如：

    1
    2
    bashCopy code
    GET /example.html HTTP/1.1

    这表示使用GET方法请求/example.html资源，并使用HTTP/1.1协议。

  2. 请求头部（Request Headers）：请求头部包含一系列用于描述请求的信息。每个头部字段以键值对的形式表示，用冒号分隔。常见的请求头部字段有:

    • Host：请求的目标主机名或IP地址
    • User-Agent：客户端的用户代理信息
    • Accept：客户端能够接收的媒体类型
    • Cookie：包含客户端的Cookie信息
    • Connection：用于客户端要求服务器使用「HTTP 长连接」机制，以便其他请求复用。

  3. 请求空行：请求头部结束后，会有一个空行表示请求头部的结束。

  4. 请求体（Request Body）：对于POST请求或其他需要发送数据的请求，请求体包含要发送给服务器的数据。在GET请求中，通常没有请求体。

响应报文的内容：

  • 状态行（Status Line）：包含HTTP协议版本、状态码和状态消息。
  • 响应头部（Response Headers）：包含用于描述响应的各种信息，如Server、Content-Type、Content-Length等。
  • 响应空行：表示响应头部的结束，用于分隔响应头部和响应体。
  • 响应体（Response Body）：响应体包含服务器返回给客户端的数据。

常见的HTTP请求方式？以及状态码？

常见的HTTP请求方式（HTTP Methods）是用于描述客户端对服务器端资源的操作类型，常见的HTTP请求方式包括：

  1. GET：用于请求获取指定资源的信息。GET请求是幂等的，即多次请求同一资源，结果相同。常用于获取页面、图片、文本等资源。
  2. POST：用于向服务器提交数据，创建新的资源。POST请求不是幂等的，即多次请求会创建多个资源。常用于提交表单数据、上传文件等操作。
  3. PUT：用于向服务器更新资源，通常要指定更新的具体位置。PUT请求是幂等的，多次请求会产生相同结果。常用于更新资源的全部内容。
  4. DELETE：用于请求删除指定资源。DELETE请求是幂等的，多次请求同一资源会产生相同结果。常用于删除资源。
  5. HEAD：类似于GET请求，但只返回资源的头部信息，不返回实际内容。常用于获取资源的元信息，如文件大小、修改时间等。
  6. OPTIONS：查询服务器的支持的请求方法。
  7. PATCH：用于对资源进行部分更新，对已有资源进行修改。

常见的HTTP状态码（HTTP Status Codes）用于表示服务器对请求的处理结果，主要包括以下几类：

  1. 1xx：信息响应，表示服务器已接收请求，需要客户端继续操作。
  2. 2xx：成功响应，表示服务器成功处理请求。
    • 200 OK：请求成功。
    • 201 Created：请求成功，服务器创建了新的资源。
    • 204 No Content：请求成功，但没有返回内容。
  3. 3xx：重定向，表示请求的资源需要重定向到其他位置。
    • 301 Moved Permanently：请求的资源被永久移动到新的位置。
    • 302 Found：请求的资源临时被移动到新的位置。
    • 304 Not Modified：资源未修改，可以直接使用缓存的内容。
  4. 4xx：客户端错误，表示客户端提交的请求有误。
    • 400 Bad Request：请求有语法错误或无法理解。
    • 401 Unauthorized：未授权，需要身份验证。
    • 403 Forbidden：服务器拒绝请求。
    • 404 Not Found：请求的资源不存在。
  5. 5xx：服务器错误，表示服务器在处理请求时发生了错误。
    • 500 Internal Server Error:与 400 类型，是个笼统通用的错误码，服务器发生了什么错误，我们并不知道。
    • 501 Not Implemented:表示客户端请求的功能还不支持，类似“即将开业，敬请期待”的意思。
    • 502 Bad Gateway:通常是服务器作为网关或代理时返回的错误码，表示服务器自身工作正常，访问后端服务器发生了错误。
    • 503 Service Unavailable表示服务器当前很忙，暂时无法响应客户端，类似“网络服务正忙，请稍后重试”的意思。

webserver项目中HTTP请求处理的细节

服务器实现的路由机制

介绍一下Epoll的IO多路复用机制

理解Epoll的IO多路复用机制需要明确以下几个关键概念：事件驱动、非阻塞IO、Epoll系统调用以及Epoll的工作模式。

  1. 事件驱动：

    在IO多路复用中，程序不再像传统阻塞IO一样轮询（或阻塞等待）每个IO通道是否有数据可读或可写，而是通过事件驱动的方式，等待通知或触发事件。当IO通道准备好时（例如有数据可读或可写），程序会收到通知，然后进行相应的处理。

  2. 非阻塞IO：

    在IO多路复用中，通常会将IO通道设置为非阻塞模式。非阻塞IO意味着当没有数据可读或可写时，IO操作不会阻塞当前线程，而是立即返回一个错误码，从而允许程序继续处理其他任务，或者等待其他IO通道。

  3. Epoll系统调用：

    在Linux系统上，Epoll是一种高效的IO多路复用机制。Epoll提供了三个系统调用：epoll_create（创建一个Epoll实例）、epoll_ctl（用于控制Epoll事件的注册和删除）和epoll_wait（等待Epoll事件的发生）。

  4. Epoll的工作模式：

    Epoll有两种工作模式：ET（边缘触发）和LT（水平触发）。

    • 边缘触发（ET）模式：只在状态发生变化时通知一次，即数据从不可读转变为可读或从不可写变为可写时触发通知。
    • 水平触发（LT）模式：只要状态处于可读或可写状态，就会不断通知，直到数据读完或写完。

epoll_fd 和 socket_fd

epoll_fd 和 socket_fd 是通过 epoll_ctl 系统调用来关联的。epoll_fd 是 Epoll 实例的文件描述符，用于管理多个 socket_fd，通过 epoll_ctl 将需要监听的 socket_fd 添加到 epoll_fd 上，然后通过 epoll_wait 等待 Epoll 事件的发生。一旦监听的 socket_fd 上有事件发生，程序可以通过返回的 struct epoll_event 结构获取相应的信息。

Epoll的实现效果，提升了多少？

介绍一下什么是双向链表，Epoll为什么要用双向链表？

双向链表（Doubly Linked List）是一种常见的链表数据结构。它与单向链表不同的地方在于，每个节点除了包含指向下一个节点的指针（通常称为”next”指针或”next”域）外，还包含指向上一个节点的指针（通常称为”prev”指针或”prev”域）。这样，==每个节点都可以通过”next”指针和”prev”指针分别连接到其后继节点和前驱节点==，从而形成一个双向的连接关系。

Epoll 的双链表结构

在事件驱动的IO多路复用中，需要频繁地插入、删除和遍历事件队列(socket_fd )，双链表可以支持快速插入、删除和反向遍历，这使得它在Epoll中非常适合用于高效地管理大量的I/O事件状态信息。

双链表可以在O(1)时间复杂度内删除节点，而单链表则需要在删除节点前找到其前驱节点，导致删除操作的时间复杂度为O(n)。

Epoll中双向链表与红黑树结构构的应用方式？双向链表怎么发挥的作用？

在 Epoll 的 IO 多路复用中，Epoll 内部使用了双链表和红黑树这两种数据结构来分别管理事件和文件描述符。

  1. 双链表的作用：
    • 双链表用于管理处于就绪状态（有数据可读或可写的）的文件描述符。Epoll 使用双链表将所有就绪的文件描述符节点连接在一起，以便在 epoll_wait 等待事件时，能够快速地找到有事件发生的文件描述符。
    • 当一个文件描述符有事件发生时，Epoll 将其对应的节点从红黑树移动到双链表中，这样可以在 O(1) 的时间复杂度内将该文件描述符添加到就绪链表中。这样避免了在红黑树中查找，从而提高了效率。
  2. 红黑树的作用：
    • 红黑树用于高效地管理所有监视的文件描述符和对应的事件信息。Epoll 使用红黑树来组织所有注册的文件描述符，以便在 epoll_wait 等待事件时，能够快速地检查是否有文件描述符处于就绪状态。
    • 红黑树是一种自平衡的二叉查找树，具有较好的平衡性质，保证了在最坏情况下的查找、插入和删除操作的时间复杂度为 O(log n)，其中 n 是红黑树中节点的数量。因此，使用红黑树可以快速地对大量的文件描述符进行查找和管理。

基本工作流程：

  1. 程序使用 epoll_create 创建一个 Epoll 实例，并获得一个文件描述符 epoll_fd。
  2. 调用 epoll_ctl 函数将需要监听的文件描述符（socket_fd）注册到 Epoll 实例中。Epoll 使用红黑树来管理这些文件描述符和对应的事件信息。
  3. 当调用 epoll_wait 等待事件时，Epoll 内部会检查红黑树中是否有文件描述符处于就绪状态。如果有，它会将就绪的文件描述符节点从红黑树移动到双链表中。
  4. epoll_wait 返回时，程序可以遍历双链表来处理所有就绪的文件描述符，进行相应的读写操作。

事件到来时，epoll 是如何实现的，主要涉及到以下几个步骤：

  1. 事件注册：
    在使用 epoll_ctl() 函数注册文件描述符时，用户态会告诉内核要关注哪些事件类型（如读、写、错误等）。这些信息会被传递到内核中，内核会在相应的数据结构中记录这些信息，同时将该文件描述符添加到红黑树中。

  2. 内核事件触发：
    当文件描述符上有事件发生时（比如有数据可读或可写），硬件或驱动程序会检测到这个事件，并将事件信息通知给内核。

  3. 内核的事件管理：
    内核会检查文件描述符的事件，并在红黑树中标记相应的文件描述符为就绪状态。这是一个内核级别的操作，不需要用户态轮询，因为内核有能力监控文件描述符的状态变化。

  4. 用户态的等待：
    当用户态的程序调用 epoll_wait() 进行事件等待时，内核会检查红黑树中哪些文件描述符已经被标记为就绪。如果有文件描述符就绪，Epoll 将其对应的节点从红黑树移动到双链表中，这样可以在 O(1) 的时间复杂度内将该文件描述符添加到就绪链表中。内核将这些文件描述符的信息返回给用户态程序，告知它们哪些文件描述符上发生了事件。

  5. 用户态事件处理：
    用户态程序收到就绪文件描述符的信息后，可以进行相应的事件处理，如读取数据、写入数据或进行其他操作。

这个过程中的关键是内核能够主动监测和管理文件描述符上的事件，并将这些事件信息传递给用户态程序，而不需要用户态程序轮询文件描述符状态。这种机制使得 epoll 更加高效，因为它避免了不必要的系统调用和循环，只在事件发生时才唤醒用户态程序。

要注意的是，内核如何监测和通知事件的细节是由操作系统的具体实现决定的，通常会涉及到硬件中断、事件队列、文件描述符管理等底层机制。不同的操作系统可能会有不同的实现方式，但 epoll 的核心思想是通过内核来管理事件，使得用户态程序能够高效地响应事件。

介绍一下什么是红黑树？

红黑树是一种自平衡的二叉查找树，通过==引入颜色属性和一系列调整操作，保持树的平衡性==，以确保查找、插入和删除操作的平均时间复杂度为 O(log n)。

二叉查找树特性：

  • 每个节点最多有两个子节点：左子节点和右子节点。
  • 左子节点的值小于等于当前节点的值，右子节点的值大于等于当前节点的值。

红黑树的特性

  • 性质1：每个节点要么是红色，要么是黑色。
  • 性质2：根节点永远是黑色的。
  • 性质3：所有的叶子节点都是空节点（即null），并且是黑色的。
  • 性质4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点。）
  • 性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

image-20230727230132432

https://blog.csdn.net/ly_6699/article/details/89792397

进程、线程和协程有什么区别？

  1. 进程（Process）：
    • 进程是计算机中运行程序的基本单位。一个进程拥有独立的地址空间、独立的系统资源（如文件描述符、内存等）和独立的执行环境。每个进程都有自己的代码段、数据段和堆栈段，它们之间不能直接共享内存。
    • 进程之间通过进程间通信（IPC，Inter-Process Communication）来实现数据交换和通信。常见的 IPC 机制包括管道、消息队列、信号量、共享内存和套接字等。
    • 进程拥有自己的进程控制块（Process Control Block，PCB），用于记录进程的状态和执行信息。进程之间的切换需要保存和恢复进程的上下文信息，因此进程切换开销较大。
  2. 线程（Thread）：
    • 线程是进程的一个执行流，一个进程可以包含多个线程。线程共享同一个进程的地址空间和系统资源，可以直接访问进程的全局变量和堆栈。
    • 线程拥有自己的执行上下文，包括程序计数器、寄存器和堆栈指针等。线程之间的切换开销相对较小，因为它们共享同一进程的资源，切换只需保存和恢复线程的执行上下文即可。
    • 多线程编程可以充分利用多核处理器的并行性，提高程序的执行效率。但多线程编程需要考虑线程同步和资源竞争问题，避免出现竞态条件等并发问题。
  3. 协程（Coroutine）：
    • 协程是一种轻量级的线程，它不是由操作系统内核来调度，而是由程序员显式地控制调度。在协程中，可以通过特定的方式进行暂停和恢复执行。
    • 协程拥有自己的执行上下文，可以在不同的协程之间进行切换。协程之间的切换开销比线程小，因为切换是由程序员手动控制的，不需要保存和恢复整个执行上下文。
    • 协程通常在同一个线程中执行，因此没有多线程的资源竞争问题。它可以用于实现高效的并发编程，例如在网络编程中实现异步操作。

C++内存泄漏的场景？怎么避免内存泄漏？

C++内存泄漏是指程序在使用完内存后，没有释放内存，导致无法再次使用，从而造成内存的浪费。

C++内存泄漏的常见场景包括：

  1. 忘记释放动态分配的内存：使用 new 或 malloc 分配了内存，但在不再需要使用时忘记了调用 delete 或 free 来释放内存。
  2. 指针的失去：将动态分配的内存赋值给指针，然后指针被重新赋值或者超出了作用域，导致原本分配的内存无法释放。
  3. 容器元素内存管理：在使用容器（如std::vector、std::map等）时，如果容器内元素是指针或动态分配的对象，在移除容器元素时需要注意正确地释放内存。

为了避免内存泄漏，可以采取以下方法：

  1. 使用智能指针：C++11引入了智能指针（如std::shared_ptr、std::unique_ptr和std::weak_ptr），它们能够==自动管理内存的释放==，避免了手动调用delete或free，大大减少了内存泄漏的可能性。
  2. RAII（资源获取即初始化）：==使用对象的构造函数申请资源，使用析构函数释放资源==，保证资源在对象的生命周期内得到正确管理，从而避免了忘记释放资源的问题。
  3. 使用容器类模板：C++标准库提供了多种容器类模板，例如std::vector、std::map等，这些容器能够自动管理元素的内存，尽量避免手动分配和释放内存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>

class MyClass {
public:
    MyClass() {
        std::cout << "Constructor" << std::endl;
    }

    ~MyClass() {
        std::cout << "Destructor" << std::endl;
    }
};

int main() {
    std::vector<MyClass*> myVec;

    myVec.push_back(new MyClass());
    myVec.push_back(new MyClass());

    // 错误的移除元素方式，没有释放内存
    myVec.erase(myVec.begin());

    // 正确的方式，释放动态分配的内存
    delete myVec[0];
    myVec.erase(myVec.begin());

    return 0;
}

介绍一下什么是B树、B+树？B+树一般怎么去用？

B树（B-tree）：

  • B树是一种自平衡的多路搜索树（也称为多路平衡查找树），可以有多个子节点。
  • 每个节点包含一个有序的关键字序列和对应的子树指针。根节点至少有两个子节点，其它非叶子节点至少有m/2个子节点（m是树的阶数）。m阶 B 树表示该树每个节点最多有 m 个子树。
  • B树的特点是==所有叶子节点都在同一层==，并且叶子节点只有关键字，指向孩子的指针为 null，使得在进行查找时磁盘IO的次数尽量减少。
  • 平衡二叉树每个节点只有一个数据和两个指向孩子的指针，而 B 树每个中间节点有 k-1 个关键字（可以理解为数据）和 k 个子树（ k介于阶数 M 和 M/2 之间，M/2 ⬆️向上取整）.
  • B树常用于文件系统和数据库索引结构的设计，适用于存储在磁盘上的大规模数据。

捕获-kMdJnv-ID-transformed

B+树（B+tree）：

  • B+树是B树的一种变体，也是一种自平衡的多路搜索树。
  • B+树与B树的区别在于：B+树的所有关键字只出现在叶子节点上，而且叶子节点之间有一个链表链接起来，使得叶子节点形成一个有序链表。
  • B+树的非叶子节点只作为索引，不保存数据，这样可以减少非叶子节点的大小，提高磁盘访问效率。
  • B+树的叶子节点存储了所有的数据，因此数据的查找效率更高。
  • B+树常用于数据库索引和文件系统中，对于范围查询的效率较高。

image-20230727235353615

应用场景

数据库索引：B+树常被用作数据库的索引结构，特别是在关系型数据库中。数据库的索引用于加速数据的查询操作，提高查询效率。B+树的特性使得它非常适合存储大量的有序数据，并能够高效地支持范围查询、精确查找和插入/删除操作。

文件系统：B+树也可以用于实现文件系统的索引结构。文件系统需要快速定位和访问文件，因此需要一种高效的索引结构。B+树可以提供快速的查找和遍历操作，并且它适合在磁盘上存储大量的文件块。

介绍一下git分支管理？什么情况下会发生冲突？

Git分支管理是指在Git中使用分支来管理代码的一种方法。分支是指代码库中的一个独立的线路，可以用于开发新功能或修复错误。分支可以相互合并，以便将新代码合并到主分支中。

常见的分支管理模型 TrunkBased 和 GitFlow ，以及阿里的分支管理模型AoneFlow。

TrunkBased模式是持续集成思想所崇尚的工作方式，==它由一个主分支和许多发布分支组成，每个发布分支在特定版本的提交节点从主分支创建出来==，用来进行上线部署以及热修复（Hotfix）;

gitflow，主要改进是加入了feature分支，这样做就避免了TrunkBased多功能开发与发布冲突的问题。

image-20230728000802925

Aone Flow 采取了另外一个思路。只存在一个 Master 分支，当要开发时，就拉出新的 Feature 分支，可以同时存在多个 Feature，当达到发布计划时，就把需要合并的多条 Feature 分支合并起来，通过后再往 Master 上合并，并且tag下来。

image-20230728000934930

介绍一下反向代理

反向代理是一种在客户端和服务器之间充当中介的服务器。它接收来自客户端的请求，并将请求转发到服务器。服务器处理请求，并将响应返回给反向代理。反向代理将响应返回给客户端。

反向代理可以用于以下目的：

  • ==负载均衡==：反向代理可以将来自客户端的请求分发到多个服务器。这可以提高服务器的性能，并防止单个服务器过载。
  • ==缓存和加速==：反向代理可以缓存来自服务器的响应。这可以提高客户端的响应速度，并减轻服务器的负担。
  • ==安全==：反向代理可以作为客户端和服务器之间的防火墙。它可以过滤恶意请求，并保护服务器免受攻击。
  • ==监控==：反向代理可以监控客户端和服务器之间的流量。它可以收集数据，并用于分析服务器的性能和安全性。

详细解释一下LRU算法？LRU算法的应用场景？

LRU算法，即最近最少使用算法，是一种缓存淘汰算法，用于确定哪些数据需要从缓存中删除，以腾出空间来存储新的数据。LRU算法的==工作原理==是：当一个数据被访问时，将其移动到缓存的头部，这样它最有可能在下次被访问时被找到。如果缓存已满，并且需要删除一个数据，则删除缓存尾部的数据，因为它是最久未被访问的数据。

LRU算法具有以下优点：

  • 可以有效地减少缓存命中率的下降。
  • 可以有效地避免缓存溢出。
  • 实现简单，易于理解。

LRU算法在以下场景中被广泛使用：

  • 操作系统的页面缓存。
  • 浏览器的缓存。
  • 数据库的缓存。
  • 网络服务器的缓存。

LRU算法是一种非常有效的缓存淘汰算法，它可以有效地提高缓存的性能。

手撕题

字符串最长无重复字串长度？（不到十分钟就说时间到了，不用写了）

双指针+unordered_set;

LRU缓存算法

定义