文件与硬盘 I/O

机械硬盘、固态硬盘、B+ 树、LSM 树、分布式文件系统 HDFS 等概念想学习；

文件控制块

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

Linux Inode 文件控制块

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

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

• 每个 inode 最多可以存储 12+256+256256+256256*256 个数据块，如果每个数据块的大小为 4k，也就是单个文件最大不超过 70G

分布式文件系统 HDFS

待写

RAID 独立硬盘冗余阵列

待写

数据结构与算法

时间复杂度与空间复杂度

• 时间复杂度

• 并不是计算程序具体运行的时间，而是算法执行语句的次数。

• O(2^n) 表示对 n 数据处理需要进行 2^n 次计算

• 多项式时间复杂度

• 非多项式时间复杂度

• 空间复杂度

• 一个算法在运行过程中临时占用存储空间大小的量度。

• O(n) 表示需要临时存储 n 个数据。

NP 问题

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

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

NP ?= P

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

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

数据结构

数组、链表、Hash 表、栈、线程调用栈、队列、树、二叉排序树、红黑树、平衡二叉树、跳表等概念.

数组

创建数组必须要内存中一块连续的空间。

数组中必须存放相同的数据类型。

随机快速读写是数组的一个重要特性，根据数

组的下标访问数据，时间复杂度为 O(1)。

链表

链表可以使用零散的内存空间存储数据。

所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。

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

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

常用算法

穷举算法

递归算法

贪心算法

动态规划

网络通信协议

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

各种网络层

网络数据包格式、物理层、链路层、网络层、传输层（TCP 协议）、应用层 HTTP 协议

运用：数据链路层负载均衡、IP 负载均衡

技术点：HTTP 请求的 7 种方法、HTTP 响应的 5 种状态、HTTP 协议版本

非阻塞网络 I/O

计算机之间如何进行网络请求？

BIO Blocking I/O 阻塞 I/O

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

技术点：Socket 接收数据，系统内核的处理过程。

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

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

非阻塞 read 操作：

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

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

非阻塞 write：

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

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