数据库面经

PostrgreSQL

MySQL 和 PgSQL 区别是什么？

PostgreSQL MySQL

• MySQL是应用开发者创建出来的DBMS；而PostgreSQL是由数据库开发者创建出来的DBMS 。换句话说，MySQL倾向于使用者的角度，回答的问题是 “你想解决的是什么问题”；而PostgreSQL倾向于理论角度，回答的问题是 “数据库应该如何来解决问题” 。
• PostgreSQL 支持 JSON、XML 等现代应用程序功能，同时 MySQL 仅支持 JSON。
• PostgreSQL 完全符合 ACID 标准，同时 MySQL 仅与 InnoDB 存储引擎 一起使用时才符合 ACID 标准。
  • ACID 标准
    1. 原子性 (Atomicity)：
       • 事务被视为一个不可分割的操作单元，要么全部执行，要么全部不执行。如果事务中的任何一部分失败，整个事务会被回滚。
    2. 一致性 (Consistency)：
       • 事务在执行前后，数据库的状态应保持一致。即事务的执行必须使数据库从一个一致性状态转变到另一个一致性状态。
    3. 隔离性 (Isolation)：
       • 事务的执行不应受到其他事务的干扰。每个事务都有其独立的执行环境，直到事务完成，它所做的更改对其他事务不可见。
    4. 持久性 (Durability)：
       • 一旦事务被提交，其结果是永久性的，即使系统崩溃，已提交的事务所做的更改也会被保留。
• 比较 PostgreSQL vs MySQL 性能， PostgreSQL 执行复杂查询时表现良好，而 MySQL 在 OLAP 和 OLTP 系统中表现良好。
  • OLAP 在线分析处理：主要用于复杂的查询和数据分析，支持决策制定。
    • 处理大量的历史数据。
    • 支持多维数据分析，通常用于数据仓库。
    • 优化查询性能，能够快速处理聚合、统计和报表生成。
    • 适合执行复杂的查询，如数据挖掘和商业智能分析。
  • OLTP 在线事物处理：主要用于日常事务处理，如订单处理、库存管理等。
    • 处理大量的短小事务。
    • 强调数据的实时性和一致性。
    • 事务执行效率高，支持高并发用户访问。
    • 适合执行简单的查询和插入、更新、删除操作。
• MySQL一般会将数据合法性验证交给客户；PostgreSQL在合法性方面做得比较严格。比如MySQL里插入 “2012-02-30” 这个时间时，会成功，但结果会是 “0000-00-00”；PostgreSQL不允许插入此值。
• MySQL 由于广泛的应用和支持，拥有庞大的用户社区和丰富的工具包。 PostgreSQL社区相对较小，但是开发者活跃，技术较为严谨，适合对安全性、标准化要求高的场景
• MySQL 更适合快速开发和高并发的应用，而 PostgreSQL 则更适合需要高度稳定性和高级特性的企业级应用

MySQL

mysql 查询会加锁吗，什么时候加什么时候不加

MySQL 查询是否加锁，取决于 SQL 语句的类型、事务隔离级别以及存储引擎（InnoDB 还是 MyISAM）

加锁语句：

• SELECT ... FOR UPDATE：排它锁
• SELECT ... LOCK IN SHARE MODE：共享锁
• 隔离级别
  • READ COMMITTED：MVCC
  • REPEATABLE READ：快照读
  • SERIALIZABLE：SELECT 会加共享锁
• REPEATABLE READ + 索引查询 + WHERE 条件命中范围查询：Gap Lock
  • Eg. 查询 不存在 的行时，会锁住一个范围，防止其他事务插入

Redis

Redis 为什么这么快

• 大部分操作在内存中完成
• 单线程模型避免多线程竞争
• IO 多路复用机制
  • select/epoll 机制：在 Redis 只运行单线程的情况下，该机制允许内核中，同时存在多个监听 Socket 和已连接 Socket。内核会一直监听这些 Socket 上的连接请求或数据请求。一旦有请求到达，就会交给 Redis 线程处理，这就实现了一个 Redis 线程处理多个 IO 流的效果。

Redis 分布式锁怎么解决超卖问题的？

同一个锁key，同一时间只能有一个客户端拿到锁，其他客户端会陷入无限的等待来尝试获取那个锁，只有获取到锁的客户端才能执行下面的业务逻辑。

比如说，用户要一次性买 10 台手机，那么避免超卖的流程如下：

• 只有一个订单系统实例可以成功加分布式锁，然后只有他一个实例可以查库存、判断库存是否充足、下单扣减库存，接着释放锁。
• 释放锁之后，另外一个订单系统实例才能加锁，接着查库存，一下发现库存只有 2 个了，库存不足，无法购买，下单失败，不会将库存扣减为-8的，就避免超卖的问题。

这种方案的缺点是同一个商品在多用户同时下单的情况下，会基于分布式锁串行化处理，导致没法同时处理同一个商品的大量下单的请求。

跳表和压缩列表是怎么实现的？

跳表

OIWiki: https://oi-wiki.org/ds/skiplist/

Redis 只有 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。

链表在查找元素的时候，因为需要逐一查找，所以查询效率非常低，时间复杂度是O(N)，于是就出现了跳表。跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快读定位数据。

那跳表长什么样呢？我这里举个例子，下图展示了一个层级为 3 的跳表。

图中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

• L0 层级共有 5 个节点，分别是节点1、2、3、4、5；
• L1 层级共有 3 个节点，分别是节点 2、3、5；
• L2 层级只有 1 个节点，也就是节点 3 。

如果我们要在链表中查找节点 4 这个元素，只能从头开始遍历链表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到节点 4，因为可以在头节点直接从 L2 层级跳到节点 3，然后再往前遍历找到节点 4。

可以看到，这个查找过程就是在多个层级上跳来跳去，最后定位到元素。当数据量很大时，跳表的查找复杂度就是 O(logN)。

那跳表节点是怎么实现多层级的呢？这就需要看「跳表节点」的数据结构了，如下：

typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

Zset 对象要同时保存「元素」和「元素的权重」，对应到跳表节点结构里就是 sds 类型的 ele 变量和 double 类型的 score 变量。每个跳表节点都有一个后向指针（struct zskiplistNode *backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。

跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。

level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。zskiplistLevel 结构体里定义了「指向下一个跳表节点的指针」和「跨度」，跨度时用来记录两个节点之间的距离。

比如，下面这张图，展示了各个节点的跨度。

第一眼看到跨度的时候，以为是遍历操作有关，实际上并没有任何关系，遍历操作只需要用前向指针（struct zskiplistNode *forward）就可以完成了。

Redis 跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

具体的做法是，跳表在创建节点时候，会生成范围为 [0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。

这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 64。

虽然我前面讲解跳表的时候，图中的跳表的「头节点」都是 3 层高，但是其实如果层高最大限制是 64，那么在创建跳表「头节点」的时候，就会直接创建 64 层高的头节点。

压缩列表

压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。

压缩列表在表头有三个字段：

• zlbytes，记录整个压缩列表占用对内存字节数；
• zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
• zllen，记录压缩列表包含的节点数量；
• zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）。

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段（zllen）的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。另外，压缩列表节点（entry）的构成如下：

压缩列表节点包含三部分内容：

• prevlen，记录了「前一个节点」的长度，目的是为了实现从后向前遍历；
• encoding，记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数。
• data，记录了当前节点的实际数据，类型和长度都由 encoding 决定；

当我们往压缩列表中插入数据时，压缩列表就会根据数据类型是字符串还是整数，以及数据的大小，会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息，这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是 Redis 为了节省内存而采用的。

压缩列表的缺点是会发生连锁更新的问题，因此连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能。

所以说，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加了，或是元素变大了，会导致内存重新分配，最糟糕的是会有「连锁更新」的问题。

因此，压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新，也是能接受的。

虽说如此，Redis 针对压缩列表在设计上的不足，在后来的版本中，新增设计了两种数据结构：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。这两种数据结构的设计目标，就是尽可能地保持压缩列表节省内存的优势，同时解决压缩列表的「连锁更新」的问题。