面试复习

[TOC]

系统

内存

物理内存和虚拟内存

物理内存就是系统硬件提供的内存大小，是真正的内存，相对于物理内存，在 Linux 下还有一个虚拟内存的概念，虚拟内存就是为了满足物理内存的不足而提出的策略，它是利用磁盘空间虚拟出的一块逻辑内存，用作虚拟内存的磁盘空间被称为交换空间（Swap Space）。

伙伴管理算法

内存管理

Linux 通过虚拟内存地址和分页的方式来管理内存，默认页大小为 4KB。

段式内存管理和页式内存管理

都是使用离散分配方式，减少内存碎片。段是信息的逻辑单位，从用户的视角来分割内存的机制，用户可见，用户知道自己的程序是如何被分段的，而且用户可以自己决定自己的程序是如何分的段。页是信息的物理单位，与源程序无关，用户不可见，用户并不知道自己的进程是如何被分页的。分页是对内存空间进行分割，主要是为了减少外部碎片，提高内存利用率。分段则是对程序内容按语义进行分割，主要是为了保护（比如代码段的内容不允许被修改）和共享（比如代码段的数据可以被共用）。

进程

1.常见的进程间通讯方式

管道
信号量
共享内存（最快，但是解决同步问题，一般用信号量或者互斥锁解决）
消息队列

2.僵尸进程和孤儿进程

孤儿进程

一个父进程退出，而它的一个或多个子进程还在运行，那么这些子进程将会成为孤儿进程，由 init 进程对它们进行状态收集工作。

僵尸进程

一个进程通过 fork 创建子进程，子进程退出后，父进程没有调用 wait 或 waitpid 获取子进程状态，那么子进程的进程描述符会保留在系统中，这种进程称之为僵尸进程。

进程创建方式

UNIX 系统通过系统调用 fork() 和 exec() 创建新进程。通过 fork() 创建的进程，子进程和父进程使用相同的代码段，子进程复制父进程的堆栈段和数据段（处于性能处理，数据在改动后才会分离）。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
    char *count = "a";
    printf("init count: %p \n", &*count);

    int rc = fork();

    if (rc < 0) { // fork fail, exit
    	fprintf(stderr, "fork failed\n");
	    exit(1);
    } else if (rc == 0){
        printf("child before manipulate: %p \n", &*count);
        ++count;
        printf("child after manipulate: %p \n", &*count);
    } else {
        printf("parent before manipulate: %p \n", &*count);
        wait(NULL);
        printf("parent after manipulate: %p \n", &*count);
    }

    return 0;
}

如果使用 exec() 创建（更像是覆盖）进程，代码段替换成新的程序的代码，废弃原有的数据段和堆栈段，并为新程序分配新的数据段与堆栈段，唯一留下的，就是进程号

进程、线程区别。为什么有了多线程还是用多进程？

进程是系统分配资源的基本单位。线程是程序中独立运行的程序片段。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，使用多线程会方便。

死锁的形成条件

死锁的四个必要条件：

互斥条件：进程所分配到的资源不允许其他进程进行访问，只能等待，直至占有该资源的进程使用完成后释放该资源。
请求和保持条件：进程获得一定的资源之后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但又不能释放已获得的资源。
不可剥夺条件：指进程已获得的资源，在未完成使用之前，不可被系统或其他进程剥夺，只能在使用完后主动释放。
环路等待：两个或两个以上的进程形成等待环路。

计算机网络

TCP

TCP 和 UDP 有什么区别

TCP 是面向连接的可靠传输协议，以字节流进行传输，受拥塞算法控制。
UDP 是无连接的传输协议，以数据报为单位，不保证顺序。

UDP 如何实现可靠传输

TCP 通过校验和、序号和确认应答、超时/差错重传以及其他优化措施（滑动窗口）实现。所以，UDP 可以通过一下方式实现可靠传输：

校验和，通过对数据部分进行哈希，然后将哈希算法类型和哈希结果在消息中发送给接收方。
序号和确认应答，加入消息序号保证顺序不会错乱，加入确认应答可以通知发送方哪些数据需要重传。
超时/差错重传，由于需要重传，所以发送方要把发送的数据放到缓存区，提高性能。
滑动窗口，除了控制发送速率，避免重复发送，以及接收方没有足够空间接受消息等问题。

浏览器输入一个网址会发生什么，用到哪些协议

域名解析，查找本地 hosts 文件是否有配置，没有就会去找 DNS 服务器解析。
建立 TCP 连接。
经由 IP 协议寻址和数据传输。
发送 HTTP/HTTPS 请求。
返回响应结果。
关闭 TCP 连接。
浏览器后续处理和渲染。

四次挥手中，TIME-WAIT状态是在哪一步？

三次握手过程第 N 条丢了会怎样？有什么现象？

第一条 SYN 丢包：第一条客户端发出的 SYN 丢包的话，服务端根本感知不到该请求，所以主要由客户端处理，会有最多三次超时重传尝试。
服务端收到 SYN 并回复的 SYN,ACK 包丢了：客户端会认为是第一条丢包了，所以客户端表现和第一条丢包流程一样。而对于服务端，此时处于 SYN_RCVD 状态，超时后未收到客户端发来的第三条 SYN，会进行数次重新发送 SYN,ACK 包（次数根据系统配置而异），重试超限后服务端会主动关闭这个连接。
客户端最后一次回复 SYN,ACK 的 ACK 包丢了：客户端收到第二条后进入 ESTABLISHED 状态（认为连接已经建立），此时有两种情况，一是此时客户端开始发送数据，则服务端也会正常进入 ESTABLISHED 状态。另一种情况是，客户端此时没有发送数据，则服务端会超时重试，发送第二条 SYN,ACK 包，超限后关闭连接。

TIME-WAIT()状态下的等待时间是多少，为什么？

2MSL（Maximum Segment Lifetime）。该状态出现在主动关闭连接的一方发送完最后一次挥手，也就是 ACK = 1 的信号结束后，主动关闭连接方所处的状态。这样设置的原因有两个：

为了保证客户端发送的最后一个ack报文段能够到达服务器。
在第四次挥手后，经过2msl的时间足以让本次连接产生的所有报文段都从网络中消失，这样下一次新的连接中就肯定不会出现旧连接的报文段了。

TCP流控制

TCP通过控制发送者发出的数据量来实现流控制，这一功能是通过滑动窗口机制来实现的。接受者的确认消息指明最后一次成功接收到报文段后可继续接收的报文段序号范围，这个可接收的序号范围称为窗口。利用通知窗口进行流控制。

TCP 粘包、拆包，以及解决方案

TCP 之所以会出现粘包问题是因为它本身是面向连接的字节流传输协议，本身就没有包的概念，TCP 要发送的数据会被先放置在数据缓冲区，接收数据也是从缓冲区获取，而缓冲区的大小即为最大报文长度，如果需要发送的数据长度大于缓冲区剩余的大小或者大于最大报文长度，则会出现拆包，当要发送的数据很少，而短时间内又有其他数据包需要发送，就会出现粘包的现象。解决方案一般有固定消息长度、设置标识符、在消息头指明消息长度。

TCP 超时时间

TCP 校验和

ref: TRANSMISSION CONTROL PROTOCOL Computing the Internet Checksum

校验和的计算：

把校验和初始化为 0，即头部的 Checksum 置为 00000000 来加入下面的计算中。
把要校验的数据（还要构造 12 字节的 IP 伪首部）相邻八位字节配对形成 16 位整数，不足的位用 0 补齐。
把第二步中得到的多个 16 位数循环进位相加，然后取和的反码得到校验和放入 Checksum 传输给接收方。
接收方校验时，和发送方一样进行 16 位循环进位加法，但是 Checksum 直接用接收到的 Checksum 而不是置为 0 加入计算，如果得到结果全部位都是 1（即结果是 -0），则校验成功。

TCP 报文长度

这个跟具体传输网络有关，以太网的 MTU 为 1500 字节，Internet 的 MTU 为 576 字节。 MTU是网络层的传输单元，那么 MSS = MTU - 20字节（IP首部） - 20字节（TCP首部）。所以以太网的 MSS 为 1460 字节，而 Internet 的 MSS 为 536 字节。

TCP 报文头结构

源端口号和目标端口号
序号
确认号（期望收到对方下一个报文段的第一个数据字节的序号）
头部长度（0.5 字节，用于计算数据在报文段的位置的偏移量）
保留位
标志位
窗口大小（指明发送窗口的大小），单位：字节
校验和（用于差错校验）
紧急指针（搭配标识位的紧急位使用，指明紧急数据的字节数）
选项（用于扩展用的字段，但是由于头部长度只有 0.5 字节，所以报文头最多 15 * 4 字节，减去前面标准头的 20 字节，这里最多可用为 40 字节）

TCP 报文的发送时机

发送缓存中的存放的数据达到 MSS 字节。
应用进程指明要求发送报文段，即 TCP 支持的 PUSH 操作。
发送方的计时器时限到了，这时也会把当前缓存的数据组装成报文发送出去。

TCP 提高传输效率

Nagle 算法和 SWS（糊涂窗口综合症）预防算法（接收缓存有一个 MSS 空间或有一半空闲的时候通知发送方）

TCP 拥塞控制

ref: TCP Congestion Control

拥塞控制用到的算法包括慢开始（slow-start）、拥塞避免（congestion avoidance）、快重传（fast retransmit）、快恢复（fast recovery）。发送方维持拥塞窗口（cwnd）的变量，根据网络拥塞程度动态调整该变量，并使发送窗口不大于该窗口大小（因为还要受接收方的通知窗口大小限制）来实现拥塞控制。

慢开始和拥塞避免

During slow start, a TCP increments cwnd by at most SMSS bytes for each ACK received that acknowledges new data. Slow start ends when cwnd exceeds ssthresh (or, optionally, when it reaches it, as noted above) or when congestion is observed.

在慢开始阶段，每接收到一个对新报文段的确认后，把 cwnd 至多增大一个 SMSS 的数值。直到达到慢开始门限值（ssthresh）或出现拥塞，慢开始结束。

During congestion avoidance, cwnd is incremented by 1 full-sized segment per round-trip time (RTT). Congestion avoidance continues until congestion is detected.

拥塞避免期间，每经过一个往返时间（RTT）就把 cwnd 加 1 个报文段的大小。拥塞避免阶段持续直到检测到网络拥塞。

When a TCP sender detects segment loss using the retransmission timer, the value of ssthresh MUST be set to no more than the value given in equation:
ssthresh = max (FlightSize / 2, 2*SMSS)

当发送方通过重传计时器监测到报文丢失的时候，必须把 ssthresh 设置成不大于 max (FlightSize / 2, 2*SMSS) 的值。其中，FlightSize 是已经发送未被确认的数据大小。某些实现里面会用 cwnd 代替 FlightSize 进行计算，这种做法可能导致增加到远大于 rwnd。在超时发生时，cwnd 会被重置为至多一个报文段大小，然后重新进入慢开始阶段。

发送方最大报文大小 SMSS：

SENDER MAXIMUM SEGMENT SIZE (SMSS): The SMSS is the size of the largest segment that the sender can transmit. The size does not include the TCP/IP headers and options.

拥塞窗口 cwnd 初始值取值：

IW, the initial value of cwnd, MUST be less than or equal to 2*SMSS bytes and MUST NOT be more than 2 segments.

慢开始门限值 ssthresh 初始值取值：

The initial value of ssthresh MAY be arbitrarily high (for example, some implementations use the size of the advertised window), but it may be reduced in response to congestion.

快重传和快恢复

A TCP receiver SHOULD send an immediate duplicate ACK when an out- of-order segment arrives.

快重传要求接收者每收到一个失序的报文段后就立即发送重复确认。此外，当接收方收到的报文填充了部分或全部失序段时，也要立即发送确认报文。

After receiving 3 duplicate ACKs, TCP performs a retransmission of what appears to be the missing segment, without waiting for the retransmission timer to expire.

对于发送者，只要连续收到三个重复确认，立马重新发送这个似乎已经丢失的报文，而不用等待重传计时器超时。

After the fast retransmit algorithm sends what appears to be the missing segment, the “fast recovery” algorithm governs the transmission of new data until a non-duplicate ACK arrives.

在快重传处理发送完疑似丢包的报文后，用快恢复算法处理传输过程直至非重复确认到达。快恢复算法主要有两个要点，一是用“乘法减小”（即上面提到的 ssthresh = max (FlightSize / 2, 2*SMSS)）算法把 ssthresh 收缩，这样可以预防网络拥塞。二是由于发送方不会认为当前网络发生拥塞，此时收缩完 ssthresh 后，把 cwnd 设置为 ssthresh 或 ssthresh + 3MSS，然后开始执行拥塞避免算法（”加法增大“），对于 cwnd 增加的 3MSS 大小应该在接收到新报文的确认后重新扣除。

HTTP

HTTP 的 Keep-Alive

当使用 Keep-Alive 模式（又称持久连接、连接重用）时，Keep-Alive 功能使客户端到服务器端的连接持续有效，当出现对服务器的后继请求时，Keep-Alive 功能避免了建立或者重新建立连接。 Keep-Alive 有一下优点：

TCP连接更少，这样就会节约TCP连接在建立、释放过程中，主机和路由器上的CPU和内存开销。
网络拥塞也减少了，拿到响应的延时也减少了。
错误处理更优雅：不会粗暴地直接关闭连接，而是report，retry。

HTTP 与 HTTPS 有啥区别？说下 HTTPS 解决了什么问题，怎么解决的？

HTTPS 是 HTTP 的安全版本，通过加入 SSL/TCL 传输层安全协议，解决了 HTTP 的会话信息明文传输导致的安全问题（消息拦截、消息篡改、消息伪造）。

说下 HTTPS 的握手过程

建立安全能力（协商加密方式）
服务端鉴别与密钥交换（服务端发送证书）
客户端鉴别与密钥交换（通过预备主密钥生成共享密钥）
客户端发送完成消息，服务端发送完成消息，握手完成（使用共享密钥发送就绪信号）

HTTPS 如何是如何保证安全的

通过消息加密防止窃听风险、通过校验机制防止篡改、通过身份证书防止冒充。 1.服务端不直接发送公钥，而是发送将证书发送给客户端，保证客户端得到的公钥不会被篡改，这样客户端发送给服务端的消息就不会被监听或篡改。 2.双方分别根据客户端随机数、服务端随机数和预备主密钥各自生成会话密钥，后续通过会话密钥对数据进行加密，这样双向的消息通信都是可靠的。 3.证书由可靠的第三方颁发，包含了颁发机构、持有者、公钥、有效期以及对应的签名信息，保证了安全性。

HTTP 优化方案

TCP 连接复用
HTTP 压缩
缓存
CDN 缓存静态文件
减少重定向，防止可能引入新的 DNS 查询、新的 TCP 连接以及新的 HTTP 请求

数据库

MySQL

MySQL 引擎类型

MyISAM：适合读取和插入数据为主，更新和删除操作少，并且对事务的完整性和并发性要求不高的表。
InnoDB：适合对事务完整性、并发性和一致性要求高，除了读取和插入，还有很多更新和删除操作的表。
Memory：存储在内存中，适合数据量小，对访问速度要求高，数据丢失不太敏感的表，如临时表。
Merge：Merge 表是由多个 MyISAM 表合并而来的虚拟表，用于突破对单个 MyISAM 表大小的限制，适合数据仓库。
CSV：按行存储，列之间以逗号分隔的 CSV 文件，CSV 引擎可以将普通的 CSV 文件作为 MySQL 表来处理，但是这种表不支持索引，适合作为数据交换用途。

行级锁、页级锁、表级锁

行级锁：颗粒度最细，只针对当前操作的行加锁，发生锁冲突的概率最低，但是加锁开销大。有共享锁和排他锁两种。并发度最高，会出现死锁。
表级锁：颗粒度最大，对全表进行加锁，发生冲突概率最高，但是实现简单，开销小。表级锁分为共享锁和排他锁两种。并发度最低，不会出现死锁。
页级锁：属于行级和表级锁的折衷方案，一次锁定相邻的一组记录，各项指标处于行级锁和表级锁之间。会出现死锁。

锁的优化策略

减少锁的持有时间：对一个方法加锁，不如对方法中需要同步的几行代码加锁。
降低锁的粒度：提高并发性。
锁分离：根据同步操作的性质，把锁分为共享锁和排他锁，共享锁之间不互斥，提高了并发性。
锁粗化：避免频繁加锁解锁，提高性能。
锁消除：避免不必要的锁。

什么是视图，游标是什么

视图：一种具有和物理表一样功能的虚拟表,由预设的查询语句定义好，使用时实时查询。视图通常是有一个表或者多个表的行或列的子集，对视图的修改会影响基本表，但是只有视图与表是一对一关系情况（还有其他条件，比如用了 LIMIT 就改不了）才能修改。

-- 人物表
CREATE TABLE person (
id int4 NOT NULL PRIMARY KEY,
name varchar(32) NOT NULL
);
-- 初始化任务表数据
INSERT INTO person values(1, 'tom');
INSERT INTO person values(2, 'tony');
-- 食物表
CREATE TABLE food (
fid int4 NOT NULL PRIMARY KEY,
uid int4 NOT NULL,
name varchar(32) NOT NULL
);
-- 初始化食物表数据
INSERT INTO food values(1, 2, 'coffee');
INSERT INTO food values(2, 2, 'bread');
INSERT INTO food values(3, 1, 'honey');


-- 定义视图（不可修改）
DROP VIEW IF EXISTS `vuf` ;
CREATE ALGORITHM = UNDEFINED 
DEFINER = `root`@`localhost` 
SQL SECURITY DEFINER 
VIEW `vuf` AS (
SELECT f.uid, p.name, f.name AS favorite_food FROM 
food AS f
LEFT JOIN 
person AS p ON p.id = f.uid
ORDER BY f.uid ASC
);

-- 定义视图（可修改），但是在查询条件加上 LIMIT 的话也会禁止修改
DROP VIEW IF EXISTS `vu` ;
CREATE ALGORITHM = UNDEFINED 
DEFINER = `root`@`localhost` 
SQL SECURITY DEFINER 
VIEW `vuu` AS (
SELECT id, name FROM person WHERE id = 1
);

游标：一种能从包含多条结果集中提取其中一条进行处理的机制。

什么是存储过程，用什么来调用

存储过程是一个预编译的 SQL 语句，优点是允许模块化的设计，就是说只需创建一次，以后在该程序中就可以调用多次。可以直接通过 CALL 关键字调用。参数有 IN、 OUT 和 INOUT 三种，默认为 IN;

IN：调用时指定，修改该参数的值不能被返回
OUT：在存储过程内部被改变，并可返回，即该参数只是用来接收结果
INOUT：调用时指定，并且可被改变和返回

-- 先把把 // 定义为执行语法,CLI 中执行需要用到，不然会尝试执行定义函数里面的语句
DELIMITER // 
CREATE PROCEDURE showPersonById(targetId int) 
BEGIN 
	SELECT * FROM person WHERE id = targetId;
END
-- 还原执行符
DELIMITER ;
-- 调用
CALL showPersonById(1);

视图和基本表的区别与联系

区别：

视图是编译好的 SQL 语句，而基本表是实际的物理数据。
基本表是内容，而视图是筛选器。
表是内模式，视图是外模式。
表属于全局模式中的表，是实表；视图属于局部模式的表，是虚表，不会暴露真实的表结构。
视图的建立和删除只影响视图本身（指的是整个 VIEW，而不是单独的记录），不影响对应的基本表。

联系：视图是基于一个或多个基本表而建立的虚拟表，它的结构来自于定义，内容来自于基本表，是基本表在逻辑意义上建立的新关系。

视图的优缺点

优点：

简单，定义好以后可以多次调用。
安全，不会暴露真实的表结构。
独立，对于视图（整体而不是单条记录记录）的删除和创建不会影响基本表。

缺点：

性能不好，简单的查询也会变得稍显复杂。
修改不方便，复杂的聚合视图基本无法修改。

MySQL binlog 的格式

Statement 模式：记录每一条修改数据的 SQL，日志量少，节约磁盘IO，对一些特殊功能（NOW()、UUID() 等函数）的复制效果不是很好。
Row 模式：Row 模式下会记录下每一行数据被修改的细节，不会出现存储过程或触发器没有被复制的问题，但是如果批量操作太多日志量会很大。
Mixed 模式：实际上就是前两种模式的结合。在Mixed模式下，MySQL会根据执行的每一条具体的sql语句来区分对待记录的日志形式，也就是在Statement和Row之间选择一种。

事务

数据库的事务是什么

对数据进行更新的一个或多个操作组成的一个执行单元，其中的操作不可分割，要么都成功，要么都失败。事务具有原子性、一致性、隔离性和持久性。

脏读、不可重复读和幻读分别指什么

脏读（Dirty Read）：事务一执行过程中修改了数据，此时事务二读取了修改后的数据，但是最终事务一没有成功提交，事务二读取到的就是脏数据。这种读取到另一个事务没有成功提交的数据称之为脏读。

不可重复读（Nonrepeatable Read）：事务二读取了两次数据，但是过程中事务一更改了数据，导致两次读取的数据不一致。这种在同一事务中，前后两次读取的数据不一致的现象就是不可重复读。

幻读（Phantom Read）：事务一前后两次读取同一范围的数据，但是两次读取过程中事务二增删了数据，导致两次读取的集合数量不一致，称为幻读。

MySQL 中 InnoDB 支持的四种事务隔离级别，以及各级别之间的区别

读未提交（Read Uncommitted）：一个事务可以读取到另一事务修改但未提交的更新数据，即事务中修改即便没有提交，别的事务也可以看到。该隔离级别下会发生脏读、不可重复读和幻读。
读已提交（Read Committed）：事务中的修改只有提交后才能被其他事务看到。解决了脏读，但是还有不可重复读和幻读现象。
可重复读（Repeated Read）：保证了同一事务先后执行的多次查询返回同一结果，看到的每行记录都是一致的，不受其他事务影响，这个级别存在幻读问题。
串行化（Serializable）：强制事务串行化执行，读写互相阻塞，效率很低，最安全，不会出现脏读、不可重复读和幻读。

MySQL 的事务回滚机制

MySQL 的 InnoDB 引擎通过 undo log 日志来实现事务回滚。当事务对数据进行修改时，InnoDB 会生成对应的 undo log，保存了事务发生之前的数据的一个版本，需要回滚时，利用其中的信息进行回滚操作。 undo log 属于逻辑日志，执行undo的时候，仅仅是将数据从逻辑上恢复至事务之前的状态，而不是从物理页面上操作实现的，这一点是不同于 redo log 的。当事务提交之后，undo log 并不能立马被删除，而是放入待清理的链表，由 purge 线程判断是否由其他事务在使用 undo 段中表的上一个事务之前的版本信息，决定是否可以清理 undo log 的日志空间。

MySQL 事务如何实现

MySQL 事务主要通过日志文件（redo log 和 undo log）、锁以及多版本并发控制（MVCC）实现。日志文件：事务过程中的操作先写入缓冲池（buffer pool）（缓存机制，由后台线程将缓冲池与磁盘数据进行同步），然后记录到 redo log buffer 和 undo log buffer，在事务提交后持久化到 redo log 和 undo log。

锁：通过锁实现事务隔离。

多版本并发控制：根据数据的 Read View（事务进行快照读生成的读视图）和事务ID（隐藏列）实现。读未提交和串行化隔离级别下都没有解决多版本并发问题，所有这个只在读已提交和可重复读隔离级别下有效。

索引

ref: MySQL常见面试题索引、表设计

查看索引

SHOW INDEX FROM tableA;

索引类型

主键索引，特殊的唯一索引，不能为空。
普通索引，使用单列作为索引，可以为空。
唯一索引，索引列的值必须唯一，但允许为空。
组合索引，在多个字段上建立的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会命中，使用组合索引时遵循最左前缀集合。
全文索引，全文索引是对文本的内容进行分词，进行搜索。

B+ Tree 索引和 Hash 索引的区别

如果是等值查询，Hash 索引有更好的查询效率。
如果是范围查询或者排序，Hash 索引完全失效。
哈希索引也不支持多列联合索引的最左匹配规则。
B+树索引的关键字检索效率比较平均，不像B树那样波动幅度大，在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。

MySQL 中 B+ Tree 的叶子节点可以存哪些东西

InnoDb 的 B+ Tree 叶子节点存的可能是整行数据或者主键的值。储存了整行数据的是主键索引，也叫聚簇索引。而存储了主键的值的是非主键索引，也叫非聚簇索引。

MyISAM 的 B+ Tree 叶子节点存的是数据记录的地址。

聚簇索引和非聚簇索引在查询数据的时候有区别吗

一般来说，利用聚簇索引查询一次就能得到数据，而非聚簇索引还要根据查到的主键值再次查询得到数据（回表）。但是有一种情况例外，就是覆盖索引，就是查询语句所用到的列的值只用从索引中就能够取得，不必从数据表中读取，换句话说查询列要被所使用的索引覆盖。

联合索引和最左前缀匹配

MySQL 的索引查询会遵循最左匹配原则，即最左优先，在检索数据时会从最左边开始匹配。所以当我们创建一个 (key1, key2, key3) 的联合索引时，相当与创建了 (key1)、(key1, key2)、(key1, key2, key3) 三个索引。因此，创建联合索引时，一般会根据业务需求，将 WHERE 子句中最频繁的列放在最前面。

什么情况下明明创建了索引，但是执行的时候并没有使用索引

查询优化器发现有更优的查询方案。在执行查询语句前，MySQL 的查询优化器会找出执行该语句的所有可能方案，对比之后找出成本最低的方案，即执行计划。如果全表扫描成本更低，就会放弃使用索引。过程大致如下：

根据搜索条件，找出所有可能使用的索引
计算全表扫描的代价
计算使用不同索引执行查询的代价
对比各种执行方案的代价，找出成本最低的那一个

实际操作中，应该设置哪些字段作为索引

主键、外键必须有索引。
经常用来与其他表进行连接的表，用来连接的字段应该有索引。
经常需要搜索查询、范围查询、或者排序的字段。
业务上需要保持唯一性的字段。

主键、外键和索引的区别

从作用来看：主键是每个表有且只有一个，用于保证数据的唯一性；外键用于建立两个表之间的连接，而且作为约束用来保证两个表之间数据一致性；索引用来加快数据检索和排序速度。从关系来看：主键可以作为另一个表的外键，主键一定会有索引；外键一定会有外键索引；索引不一定是主键或外键。

SQL 相关

SQL 语句优化方向

精简查询字段，避免使用 SELECT * FROM tableA，读取字段内容也会消耗性能。
优化索引，主要原则就是应尽量避免全表扫描，应该考虑在 WHERE 及 ORDER BY 涉及的列上建立索引。
使用联合索引时，注意索引列的顺序。
分页查询，加 LIMIT 防止查询数据量过大。
优化查询语句，如：避免在 WHERE 子句中使用 !=；使用 LIKE 关键字最好固定左边以免索引失效；使用默认值代替 NULL，否则使用时 IS NULL 或者 IS NOT NULL 可能会全表扫描。
限制索引数量，避免避免增加更新/插入时的系统开销。

CHAR 和 VARCHAR 的区别

char 的长度固定，而 varchar 的长度是不固定的，所以 char 的会占用更多空间，但是读取速度更快。
char 在取值的时候会把存值后面的空格去除掉，varchar 如果后面有空格则会保留；
存储方式不一样，不同字符集的字符占用字节不一样。

怎么找出最后一次插入时分配了哪个自动增量？

变量 LAST_INSERT_ID 将返回由 auto_increment 分配的最后一个值，并且不需要指定表名称。但是这个值会在 MySQL 重启重置为 0，所以不太准确。

SHOW VARIABLES LIKE ‘LAST_INSERT_ID’;

BLOL 和 TEXT 有什么区别

TEXT 与 BLOB 的主要差别就是 BLOB 保存二进制数据，TEXT 保存字符数据，因此 BLOB 区分大小写，而 TEXT 不区分大小写。

-- 建表
CREATE TABLE `person` (
  `id` int NOT NULL,
  `bl` blob,
  `te` text
)
-- 初始化数据
INSERT INTO person (id, bl, te) VALUES (1, 'abc', 'abc');
-- 查询
SELECT * FROM person WHERE bl = 'abc'; -- 1
SELECT * FROM person WHERE bl = 'ABC'; -- 0
SELECT * FROM person WHERE te = 'abc'; -- 1
SELECT * FROM person WHERE te = 'ABC'; -- 1

MySQL 怎么优化 DISTINCT？

ref: DISTINCT Optimization

在大多数情况下，DISTINCT子句可以视为GROUP BY的特殊情况。例如，下面的两个查询是等效的：

SELECT DISTINCT c1, c2, c3 FROM t1
WHERE c1 > const;

SELECT c1, c2, c3 FROM t1
WHERE c1 > const GROUP BY c1, c2, c3;

由于这个等效性，适用于 GROUP BY 查询的优化也可以被应用于有 DISTINCT 子句的查询。所以改写成 GROUP BY 形式再优化。

通用的 SQL 函数

SQL 的标准内置函数，不同的方言数据库基本都支持的。常用的有：

算术类：ABS()、MOD()、ROUND() 等。
字符串类：CONCAT()、LENGTH()、LOWER()、UPPER() 等。
日期类：CURRENT_DATE()、CURRENT_TIME()、CURRENT_TIMESTAMP() 等。
转换类：CAST() 等

MySQL 有关权限的表有哪些

ref: MySQL 用户权限管理

mysql.user 表：记录允许连接到服务器的用户帐号信息，里面的权限是全局级的。
mysql.db 表：存放数据库级别的权限，记录哪些主机的哪些用户各个数据库上的操作权限。
mysql.tables_priv 表：存放表级别的权限，决定了来自哪些主机的哪些用户可以访问数据库的这个表。
mysql.columns_priv 表：存放列级别的权限，决定了来自哪些主机的哪些用户可以访问数据库表的这个字段
mysql.procs_priv 表：存放存储过程和函数级别的权限。

MySQL 外连接、内连接和自连接的区别

外连接：筛选出两张表中匹配的数据，以及主表中未匹配的数据，即主表的所有数据都会被筛选出来。
内连接：筛选出两张表中匹配的数据。
自连接：针对相同的表进行的连接被称为“自连接”。

完整性约束包括哪些？

数据完整性是指数据的精确性和可靠性。主要有四类：

实体完整性：表的每一行数据是表中的唯一实体。
域完整性；表中的列数据满足定义好的类型和取值范围。
参照完整性：两个表的主键的值和外键的值保持一致，保证表之间的数据一致性。
用户定义的完整性：用户根据需要制定的一些特殊约束（非空约束、唯一性约束等等）。

如何确保表格里的字段只接受特定范围内的值？

在对应的列创建 CHECK 约束。

Redis

Redis 的 hash 冲突是怎么解决的，rehash 的过程是怎么样的

ref: 美团针对Redis Rehash机制的探索和实践

在Redis中，键值对（Key-Value Pair）存储方式是由字典（Dict）保存的，而字典底层是通过哈希表来实现的。Redis 通过链表（next 指针）来解决 hash 冲突。 Hash 冲突（负载因子）超过某个阈值时，出于链表性能的考虑，会进行 Resize 的操作。 Redis 使用了渐进式 rehash 机制，避免 rehash 对服务器性能造成影响，渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。

Redis 的持久化方式

ref: Redis 持久化

Redis 提供了两种持久化的方式，分别是 RDB（Redis DataBase）和 AOF（Append Only File）。 RDB：将 Redis 某一时刻的数据持久化到磁盘中，是一种快照式的持久化方法。 AOF：将 Redis 执行过的所有写指令记录下来，在下次 Redis 重新启动时，只要把这些写指令从前到后再重复执行一遍，就可以实现数据恢复了

其他

数据结构与算法

怎么把一颗二叉树原地变成一个双向链表？

中序遍历，遍历过程中添加节点的指针信息。

一致性哈希是什么

一致性哈希是一种特殊的哈希算法，解决了简单哈希算法在分布式哈希表中的动态伸缩问题。通过构造环形的哈希空间，使得节点变更时的数据迁移只影响两个节点，不会造成全局的数据迁移问题。一致性哈希的负载不均衡和由此可能带来的雪崩效应可以通过虚拟节点来解决，即一台机器复制出多个虚拟节点，交叉分布在环中。

红黑树

内存池

线程池实现

先判断线程池中线程的数量是否超过核心线程数，如果没有超过核心线程数，就创建新的线程去执行任务；如果超过了核心线程数，就进入到下面流程。
判断任务队列是否已经满了，如果没有满，就将任务添加到任务队列中；如果已经满了，就进入到下面的流程。
再判断如果创建一个线程后，线程数是否会超过最大线程数，如果不会超过最大线程数，就创建一个新的线程来执行任务；如果会，则进入到下面的流程。
执行拒绝策略。