文件与硬盘 I/O

机械硬盘

固态硬盘

存储结构

B+ 树

LSM 树

文件控制块

文件系统将硬盘空间以块为单位进行划分，每个文件占据若干个块，然后再通过一个文件控制块 FCB 记录每个文件占据的硬盘数据块。每个块大小是4K。

Linux Inode 文件控制块

inode 中记录着文件权限、所有者、修改时间和文件大小等文件属性信息，以及文件数据块硬盘地址索引。

inode 是固定结构的，能够记录的硬盘地址索引数也是固定的，只有 15 个索引。

每个 inode 最多可以存储12+256+256256+256256*256 个数据块，如果每个数据块的大小为 4k，也

就是单个文件最大不超过70G。

RAID 独立硬盘冗余阵列

RAID0 RAID1 RAID10 RAID5 RAID6



分布式文件系统 HDFS

HDFS中的每个文件块大小是64M。HDFS系统针对的是大文件的分布式文件存储系统。



数据结构与算法

时间复杂度与空间复杂度

时间复杂度：执行语句的次数

空间复杂度：运行过程中临时占用存储空间大小的量度

NP 问题

P 问题：能在多项式时间复杂度内解决的问题。

NP 问题：能在多项式时间复杂度内验证答案正确与否的问题。

NP ?= P

NP-hard 问题：比 NP 问题更难的问题（NP问题的解法可以规约到 NP-hard 问题的解法）

NP 完全问题：是一个 NP-hard 问题，也是一个 NP 问题。



数据结构

数组 链表 Hash 表（Hash 冲突）

链表中增删数据要比数组性能好的多

数组链表结合，实现快速查找和快速增删

栈：后进先出 线程调用栈

队列：先进先出 生产者消费者

用队列搜索好友中关系最近的有钱人

用队列搜索最短路径

树

二叉排序树

定义：左子树上所有结点的值均小于或等于它的根结点的值。

右子树上所有结点的值均大于或等于它的根结点的值。

左、右子树也分别为二叉排序树。

不平衡的二叉排序树

平衡二叉（排序）树

从任何一个节点出发，左右子树深度之差的绝对值不超过1。

左右子树仍然为平衡二叉树。

维持平衡：旋转二叉树恢复平衡

红黑（排序）树

定义：每个节点只有两种颜色：红色和黑色。

根节点是黑色的。

每个叶子节点（NIL）都是黑色的空节点。

从根节点到叶子节点，不会出现两个连续的红色节点。

从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

维持平衡：增删节点的时候，红黑树通过染色和旋转，保持红黑树满足定义。

红黑树 VS 平衡二叉树

红黑树最多只需3次旋转就会重新达成红黑平衡，时间复杂度 O(1)。

在大量增删的情况下，红黑树的效率更高。

红黑树的平衡性不如平衡二叉树，查找效率要差一些。

跳表



常用算法

穷举算法

递归算法

贪心算法

动态规划

递归算法（快速排序算法）：时间复杂度： n * log(n)

贪心算法：不一定可以得到最优解

改进贪心算法 - 迪杰斯特拉算法（最快路径）

迪杰斯特拉算法的核心是找到起点到每个节点的最快路径

动态规划算法解决背包问题

遗传算法解决背包问题

基因编码与染色体

适应函数与控制参数

选择算法：轮盘赌选择、随机竞争选择、均匀排序

交叉遗传

遗传算法得到的不是最优解，但是能够利用最少的资源最快得到解。



网络通信协议

OSI 七层模型和 TCP/IP 四层模型

网络数据包格式

物理层：物理层负责数据的物理传输

链路层：链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信

数据链路层负载均衡

网络层：网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标服务器

IP 负载均衡

传输层（TCP协议）

IP 协议不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通

信的稳定可靠，需要传输层协议 TCP。

TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。

TCP作为一个比较基础的通讯协议，有很多重要的机制保证了TCP协议的可靠性和强壮性：

使用序号、无错传输、使用确认和计时器来检测和纠正丢包或者延时、流量控制、拥塞控制

TCP 建立连接的3次握手

TCP 关闭连接4次挥手（双全工）

应用层 HTTP 协议：互联网应用需要在全球范围为用户提供服务，将全球的应用和全球的用户联系在一起，需要一个统一的应用层协议，这个协议就是 HTTP 协议。

HTTP 请求的7种方法

Get：只读请求

Head：和 get 方法一样，但是只返回响应头。

Post：提交请求。

Put：上传请求。

Delete：删除 URL 标识的资源。

Trace：回显服务器收到的请求，用以测试或者诊断。

Options：请求服务器返回支持的所有 HTTP 请求方法，测试服务器是否正常。

HTTP 响应的5种状态

1xx消息——请求已被服务器接收，继续处理

2xx成功——请求已成功被服务器接收、理解、并接受

3xx重定向——需要后续操作才能完成这一请求

4xx请求错误——请求含有词法错误或者无法被执行

5xx服务器错误——服务器在处理某个正确请求时发生错误

HTTP 协议版本

HTTP/2 引入了 HTTP“流”的概念，允许将不同的 HTTP 并发地复用到同一 TCP 连接上， 使浏览器更高效地复用 TCP 连接。

HTTP/3 不是使用 TCP 作为会话的传输层，而是使用 QUIC （一种新的互联网传输协议）。多个QUIC 流共享相同的 QUIC 连接，因此不需要额外的握手和慢启动来创建新的 QUIC 流。

非阻塞网络 I/O

BIO Blocking I/O 阻塞 I/O

阻塞 I/O：进行 I/O 操作时，用户线程会一直阻塞，直到读操作或者写操作完成。

非阻塞 I/O（ Non-Blocking I/O ）

非阻塞 I/O：I/O 操作立即返回,发起线程不会阻塞等待。

非阻塞 read 操作：

• Socket 接收缓冲区有数据，读 n 个（不保证数据被读完整，因此有可能需要多次读）。

• Socket 接收缓冲区没数据，则返回失败（不会等待）。

非阻塞write：

• Socket 发送缓冲区满，返回失败（不会等待）。

• Socket 发送缓冲区不满，写 n 个数据（不保证一次性全部写入，因此可能需要多次写）。

Java NIO (New I/O)

系统 I/O 复用方式：select，poll，epoll