阿Q技术站

深浅色

饿了么一面凉经 ​

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

1、字符类型和数字类型在内存中占用是多少？ ​

  1. 字符类型（如 char、wchar_t等）通常占用固定大小的内存空间，具体取决于编程语言和字符编码方案。在许多编程语言中，一个字符通常占用1个字节（8位），例如ASCII编码，每个字符用一个字节表示；而在一些语言中，特别是涉及多字节字符编码（如UTF-8、UTF-16）的情况下，一个字符可能会占用更多的空间，如2个字节或4个字节。
  2. 数字类型（如整数、浮点数等）的大小取决于具体的类型和编程语言。通常情况下：
    • 整数类型的大小可以是1个字节（8位）、2个字节（16位）、4个字节（32位）、8个字节（64位）等，具体取决于编程语言和平台。例如，在C语言中，int类型通常是4个字节（32位）。
    • 浮点数类型的大小也因语言和平台而异。通常，单精度浮点数（float）占用4个字节（32位），双精度浮点数（double）占用8个字节（64位）。

2、磁盘的扫描算法？ ​

  1. 顺序扫描（Sequential Scan）：顺序扫描是一种简单直观的扫描方式，从磁盘的起始位置开始，按照顺序依次读取每个数据块，直到找到目标数据块或到达磁盘末尾。这种方式适用于数据分布较为均匀的情况，但在大规模数据存储中可能效率较低。
  2. 循环扫描（Circular Scan）：循环扫描是一种改进的扫描方式，当扫描到达磁盘末尾时，会回到磁盘起始位置继续扫描，形成一个循环。这种方式可以减少寻址的跨越，提高效率。
  3. 扇区扫描（Sector Scan）：扇区扫描是指按照磁盘的扇区（sector）进行扫描，每个扇区通常包含多个数据块。扇区扫描可以减少磁头的移动次数，提高读取效率。
  4. 最佳位置优先（Shortest Seek Time First, SSTF）：SSTF 算法是一种基于磁头移动距离最短的原则来选择下一个读取位置的算法。在磁盘扫描中，选择离当前磁头位置最近的数据块进行读取，以减少磁头的移动时间。
  5. 先来先服务（First Come First Serve, FCFS）：FCFS 算法是一种简单的扫描方式，按照请求的顺序进行扫描。但这种方式可能会导致磁头在磁盘上来回移动，效率较低。
  6. 电梯算法（Elevator Algorithm）：电梯算法模拟电梯的运行方式，在一个方向上连续扫描直到遇到最远的请求，然后改变方向继续扫描。这种方式可以减少磁头的移动次数，提高效率。

3、读写锁是怎么用的？它的实现原理是什么？ ​

读写锁（Read-Write Lock）是一种并发控制机制，用于提高多线程环境下读取和写入操作的效率。它允许多个线程同时读取共享数据，但在写操作时会阻塞其他线程的读取和写入操作。

用法 ​

读写锁一般包含两种状态：读模式和写模式。在读模式下，多个线程可以同时获取读锁并读取共享数据；在写模式下，只允许一个线程获取写锁来修改共享数据，其他线程无法获取读锁或写锁。

基本用法如下：

  • 读取数据时，首先获取读锁（read_lock.acquire()），读取完毕后释放读锁（read_lock.release()）。
  • 写入数据时，首先获取写锁（write_lock.acquire()），写入完毕后释放写锁（write_lock.release()）。
实现原理 ​

读写锁的实现原理可以简单概括为：

  1. 维护两种锁：读锁和写锁。
  2. 当有线程请求读锁时，如果当前没有线程持有写锁，则允许该线程获取读锁；如果有线程持有写锁，则该线程需要等待。
  3. 当有线程请求写锁时，如果当前没有线程持有读锁或写锁，则允许该线程获取写锁；如果有线程持有读锁或写锁，则该线程需要等待。

具体实现可以使用计数器来记录读锁和写锁的数量，以及条件变量来控制线程的等待和唤醒。一种简单的实现方式是使用 Python 的 threading 模块：

python
import threading

class RWLock:
    def __init__(self):
        self._lock = threading.Lock()
        self._readers = 0
        self._writer = False

    def acquire_read(self):
        with self._lock:
            while self._writer:
                self._lock.wait()
            self._readers += 1

    def release_read(self):
        with self._lock:
            self._readers -= 1
            if self._readers == 0:
                self._lock.notifyAll()

    def acquire_write(self):
        with self._lock:
            while self._readers > 0 or self._writer:
                self._lock.wait()
            self._writer = True

    def release_write(self):
        with self._lock:
            self._writer = False
            self._lock.notifyAll()

# 使用示例
lock = RWLock()

# 读取数据
lock.acquire_read()
# 读取操作
lock.release_read()

# 写入数据
lock.acquire_write()
# 写入操作
lock.release_write()

4、B+ 树和 B 树区别？ ​

  1. 结构差异：
    • B树：B树是一种多路搜索树，每个节点包含多个子节点。B树的非叶子节点称为索引节点，叶子节点存储实际数据或指向数据的指针。B树节点中的键值按序排列，子节点中的键值范围划分了父节点中的键值范围。
    • B+树：B+树也是一种多路搜索树，但与B树不同的是，B+树的非叶子节点仅用作索引，不存储实际数据。所有叶子节点都按序连接，形成一个有序链表，便于范围查询和遍历。
  2. 节点结构：
    • B树：B树的节点既存储键值，又存储子节点指针。
    • B+树：B+树的非叶子节点仅存储键值和子节点指针，不存储实际数据，而叶子节点存储实际数据。
  3. 查找方式：
    • B树：在B树中进行查找时，可以在非叶子节点中进行查找，如果找到键值，则向下继续查找；如果未找到，则根据键值范围确定下一步查找的子节点。
    • B+树：B+树的查找必须从根节点开始，直到叶子节点。叶子节点是一个有序链表，可以进行范围查询和遍历。
  4. 适用场景：
    • B树：B树适用于数据库索引和文件系统等需要随机访问的场景，因为它可以在非叶子节点中进行查找，减少磁盘IO次数。
    • B+树：B+树适用于需要范围查询和排序的场景，例如数据库的范围查询和排序操作。
  5. 磁盘IO：
    • B树：由于B树的非叶子节点也存储数据，因此在进行范围查询时，可能需要多次IO操作。
    • B+树：B+树的叶子节点形成了一个有序链表，范围查询只需要沿着链表遍历，减少了IO操作次数。

5、什么数据库适合用 B+ 树作为索引、什么数据库采用 B 树作为索引？ ​

适合使用B+树作为索引的数据库： ​
  1. 关系型数据库：大多数关系型数据库（如MySQL、PostgreSQL、Oracle等）使用B+树作为索引结构。
  2. 需要范围查询和排序：B+树的叶子节点形成有序链表，适合范围查询和排序操作，因此适合需要频繁进行这类操作的数据库。
  3. 需要支持高并发读取：B+树的多路搜索树结构可以提高并发读取的效率，适合需要大量读取操作的数据库。
  4. 需要支持快速插入和删除：B+树的平衡性和局部性使得插入和删除操作效率较高，适合需要频繁进行这类操作的数据库。
适合使用B树作为索引的数据库： ​
  1. 文件系统：由于文件系统需要频繁进行随机访问，因此通常使用B树作为索引结构。
  2. 数据库缓存索引：有些数据库（如Redis等）在内存中使用B树作为索引结构，因为内存中的数据可以快速访问，不需要B+树的范围查询和排序特性。
  3. 需要支持频繁的随机访问：B树在非叶子节点也存储数据，因此可以在非叶子节点进行查找，适合需要频繁进行随机访问的场景。
  4. 对内存占用要求较高：B树的节点结构相对简单，存储的数据量相对较少，适合对内存占用有要求的场景。

6、进程间通信如何实现的？ ​

  1. 管道（Pipe）：管道是一种半双工的通信方式，适用于具有亲缘关系的进程间通信。管道有两种：匿名管道和命名管道。匿名管道只能在具有父子关系的进程之间使用，而命名管道允许无关的进程之间进行通信。
  2. 消息队列（Message Queue）：消息队列是一种进程间通信的方式，允许一个进程向另一个进程发送消息。消息队列有一个存放消息的队列，一个进程向队列中发送消息，另一个进程从队列中读取消息。
  3. 信号量（Semaphore）：信号量是一种用于多进程间同步的机制，可以用来控制多个进程对共享资源的访问。信号量可以是计数器，用来表示可用资源的数量，进程可以通过对信号量进行操作来获取或释放资源。
  4. 共享内存（Shared Memory）：共享内存是一种进程间通信的方式，允许多个进程访问同一块内存区域。多个进程可以将共享内存映射到它们的地址空间中，从而实现对同一块内存区域的访问。
  5. 套接字（Socket）：套接字是一种网络编程中用于实现进程间通信的机制，可以在同一台主机的不同进程间进行通信，也可以在不同主机之间进行通信。套接字可以实现多种通信方式，如TCP和UDP。
  6. 信号（Signal）：信号是一种用于通知进程发生某种事件的机制，如中断信号（SIGINT）用于通知进程接收到用户键盘输入中断。

7、进程和线程之间的区别？ ​

  1. 定义：
    • 进程是程序在计算机上的一次执行过程，是系统进行资源分配和调度的基本单位。
    • 线程是进程中的一个执行单元，是操作系统能够进行运算调度的最小单位，也是程序执行流的最小单元。
  2. 资源拥有：
    • 进程拥有独立的地址空间、内存、文件描述符等资源，进程间的通信需要通过特定的机制进行。
    • 线程与所属进程共享同一地址空间和大部分其他资源，线程间通信比进程间通信更加方便快捷。
  3. 切换代价：
    • 由于进程拥有独立的资源，进程间切换的代价相对较高，涉及到切换地址空间、内存映射、文件描述符等。
    • 线程切换的代价相对较低，因为线程共享大部分资源，只需要切换寄存器和栈即可。
  4. 并发性：
    • 进程是独立的执行流，进程间并发执行，互不干扰。
    • 线程是进程的实体，同一进程内的多个线程可以并发执行，共享进程的资源。
  5. 创建销毁开销：
    • 创建和销毁进程的开销相对较大，涉及到资源的分配和释放。
    • 创建和销毁线程的开销相对较小，通常只需分配或释放一些内存空间。
  6. 灵活性：
    • 进程间相互独立，灵活性较低，通信和同步需要额外的机制。
    • 线程间共享同一进程的资源，灵活性较高，可以直接共享数据、通信和同步。

8、栈、队列、二叉树的实现过程，它们的使用场景？ ​

栈（Stack）的实现过程及使用场景： ​

实现过程： ​
  • 栈是一种后进先出（LIFO）的数据结构，可以通过数组或链表实现。
  • 使用数组实现时，需要一个指针来指向栈顶元素，入栈操作将元素放入数组对应位置并将指针加一，出栈操作将指针减一并返回对应元素。
  • 使用链表实现时，需要一个指针指向链表头部作为栈顶，入栈操作将元素插入链表头部，出栈操作将头部元素删除并返回。
使用场景： ​
  • 函数调用：函数调用时会使用栈来保存当前函数的上下文信息，包括局部变量、参数、返回地址等。
  • 表达式求值：中缀表达式转后缀表达式时可以使用栈来保存运算符，然后按照后缀表达式的顺序进行计算。
  • 浏览器历史记录：浏览器的前进后退功能可以使用两个栈来实现，一个栈保存前进的页面，另一个栈保存后退的页面。

队列（Queue）的实现过程及使用场景： ​

实现过程： ​
  • 队列是一种先进先出（FIFO）的数据结构，同样可以使用数组或链表实现。
  • 使用数组实现时，需要两个指针分别指向队列的头部和尾部，入队操作将元素放入尾部并将尾指针加一，出队操作将头部元素取出并将头指针加一。
  • 使用链表实现时，需要一个指针指向队列头部作为头指针，另一个指针指向队列尾部作为尾指针，操作类似于数组实现。
使用场景： ​
  • 任务调度：操作系统中的任务调度通常使用队列来实现，按照任务的优先级将任务放入队列中进行调度。
  • 缓冲区：网络通信或IO操作中经常使用队列作为缓冲区，暂存需要发送或接收的数据。
  • 广度优先搜索（BFS）：图的广度优先搜索算法通常使用队列来保存待访问的节点。

二叉树的实现过程及使用场景： ​

实现过程： ​
  • 二叉树是一种每个节点最多有两个子节点的树结构，通常使用指针实现。
  • 每个节点包含一个数据元素和指向左右子节点的指针，可以使用递归或迭代方式实现插入、删除、查找等操作。
使用场景： ​
  • 文件系统：操作系统中的文件系统通常使用树结构来组织文件和目录，方便查找和管理。
  • 数据库索引：数据库中的索引通常使用二叉树或其变种（如平衡二叉树、B树、B+树等）来实现，加快数据的查找速度。
  • 表达式解析：将中缀表达式转换为后缀表达式时可以使用二叉树来表示表达式的结构，并按照后缀表达式的顺序进行计算。

9、介绍一下红黑树，以及查找过程？ ​

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位表示节点的颜色，可以是红色或黑色。

红黑树的特性：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点是黑色。
  3. 每个叶子节点（NIL节点，空节点）是黑色。
  4. 如果一个节点是红色，则它的子节点必须是黑色。
  5. 从任意节点到其每个叶子节点的路径都包含相同数量的黑色节点。

这些特性确保了红黑树的关键性质：从根到叶子的最长路径不超过最短路径的两倍，因此红黑树是近似平衡的。

红黑树的查找过程： ​

  1. 从根节点开始，将待查找的值与当前节点的值比较。
  2. 如果待查找的值等于当前节点的值，则返回当前节点。
  3. 如果待查找的值小于当前节点的值，则继续在当前节点的左子树上查找。
  4. 如果待查找的值大于当前节点的值，则继续在当前节点的右子树上查找。
  5. 重复上述步骤，直到找到待查找的值或遇到叶子节点。

在红黑树中，查找操作的时间复杂度为 O(log n)，其中 n 为树中节点的数量。由于红黑树是一种平衡树，它保持了树的高度较低，使得查找操作效率较高。

10、红黑树插入一个数据，旋转逻辑是什么？ ​

  1. 情况1：插入节点为根节点。

    将插入节点涂为黑色，保持性质2。

  2. 情况2：插入节点的父节点为黑色。

    由于插入节点的父节点为黑色，不会破坏性质4，插入完成。

  3. 情况3：插入节点的父节点为红色，且叔节点也为红色。

    将插入节点的父节点和叔节点涂为黑色，将祖父节点涂为红色，并以祖父节点为当前节点进行下一轮操作，即向上继续检查是否破坏了性质4。

  4. 情况4：插入节点的父节点为红色，叔节点为黑色（或NIL节点），且插入节点为其父节点的右子节点（父节点为祖父节点的左子节点）。

    将父节点作为旋转中心进行左旋操作，使得插入节点变为其父节点，转为情况5。

  5. 情况5：插入节点的父节点为红色，叔节点为黑色（或NIL节点），且插入节点为其父节点的左子节点（父节点为祖父节点的左子节点）。

    将父节点涂为黑色，祖父节点涂为红色，以祖父节点为中心进行右旋操作，完成插入后的平衡。

11、MySQL 如何对数据进行一个恢复的？ ​

  1. 备份恢复：
    • 使用MySQL提供的mysqldump工具或第三方备份工具对数据库进行定期备份。
    • 当数据丢失或损坏时，可以使用备份文件进行恢复。恢复过程包括停止MySQL服务、恢复备份文件、启动MySQL服务等步骤。
  2. 二进制日志（Binary Log）恢复：
    • MySQL通过二进制日志记录数据库的所有修改操作，可以通过回放二进制日志来恢复数据。
    • 使用mysqlbinlog工具将二进制日志转换成SQL语句，并将其应用到数据库中，以恢复数据。
  3. 事务日志（Transaction Log）恢复：
    • MySQL使用事务日志记录每个事务的操作，可以通过回滚事务日志来恢复到某个时间点的数据库状态。
    • 使用mysqlbinlog工具将事务日志转换成SQL语句，并将其应用到数据库中，以恢复数据。
  4. InnoDB引擎的恢复：
    • InnoDB引擎支持自动崩溃恢复和手动恢复。
    • 自动崩溃恢复会在MySQL重新启动时自动检查并恢复InnoDB存储引擎中的数据。
    • 手动恢复可以通过innodb_force_recovery参数设置InnoDB引擎的恢复级别，以修复某些损坏的数据页。
  5. 物理备份与恢复：
    • 使用物理备份工具（如Percona XtraBackup）对MySQL数据库进行备份，可以实现全量备份和增量备份。
    • 在数据丢失或损坏时，可以通过物理备份文件进行恢复。

12、脏读和幻读？ ​

  1. 脏读（Dirty Read）：
    • 脏读指一个事务读取到了另一个事务未提交的数据。当一个事务读取了另一个事务中正在修改的数据，而这个修改操作最终没有提交，那么该事务读取到的数据就是脏数据，称为脏读。
    • 例如，事务A修改了一行数据，但是还未提交，事务B读取到了这个未提交的数据，如果事务A在后续发生了回滚操作，那么事务B读取到的数据就是脏数据。
  2. 幻读（Phantom Read）：
    • 幻读指一个事务在读取了一组数据后，另一个事务插入了新的数据，当第一个事务再次读取相同的数据时，会发现多了一些数据。这种现象就像发生了幻觉一样，所以称为幻读。
    • 例如，事务A根据某个条件查询了一组数据，事务B插入了符合条件的新数据，当事务A再次查询相同条件的数据时，会发现有新插入的数据，导致幻读。

13、MySQL 存储引擎有哪些？ InnoDB 和 MyISAM 对事务的支持？ ​

  1. InnoDB：InnoDB是MySQL默认的存储引擎，它支持事务、行级锁和外键等高级功能，适合于需要高并发和数据完整性要求较高的场景。
  2. MyISAM：MyISAM是MySQL的另一种存储引擎，它不支持事务和行级锁，但对于读密集型的应用具有较好的性能，适合于数据不太频繁更新的场景。
  3. MEMORY：MEMORY存储引擎将表数据存储在内存中，适合于临时表和需要快速访问的数据存储，但是在重启MySQL时数据会丢失。
  4. CSV：CSV存储引擎将数据存储在CSV文件中，适合于导入导出数据。
  5. Archive：Archive存储引擎用于存储归档数据，支持高压缩比和快速插入，但不支持索引。
  6. Blackhole：Blackhole存储引擎将写入的数据丢弃，用于测试和日志复制等场景。
  7. Federated：Federated存储引擎可以在不同的MySQL服务器之间实现数据共享。

对于事务支持方面，InnoDB和MyISAM有以下区别：

  • InnoDB：支持事务，具有ACID特性（原子性、一致性、隔离性、持久性），支持行级锁，适合于高并发和要求数据完整性的应用场景。
  • MyISAM：不支持事务，不具备ACID特性，表级锁会导致并发性能较差，适合于读操作频繁、写操作较少的应用场景，如日志记录等。

14、数据的范式？ ​

  1. 第一范式（1NF）：确保每个列都是不可分割的原子值，即每个列不包含多个值或重复的组合值。
  2. 第二范式（2NF）：要求表中的每个非主属性完全依赖于候选键，而不是依赖于候选键的一部分。
  3. 第三范式（3NF）：要求表中的每个非主属性既不传递依赖于候选键，也不依赖于其他非主属性。
  4. 巴斯-科德范式（BCNF）：是第三范式的一种扩展，要求每个非平凡函数依赖于超键。
  5. 第四范式（4NF）：要求表中的每个多值依赖都是由其候选键的一个超键决定的。
  6. 第五范式（5NF）：要求在表中不存在任何非平凡的联合依赖。