本周学习内容

1.文件与硬盘I/O

1. 硬盘运行原理

2. B+ 树

3. LSM 树

4. 文件控制块

5. RAID 独立硬盘冗余阵列

6. 分布式文件系统HDFS

2.数据结构与算法

2.1算法术语

时间复杂度

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

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

• 多项式时间复杂度

• 非多项式时间复杂度



空间复杂度

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

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



NP 问题

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

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

• NP ?= P

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

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

2.2数据结构

• 数组

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

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

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

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

• 链表

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

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

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

• 栈

• 数组和链表都被称为线性表。

• 栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。

• 队列

• 队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。

• 典型应用场景：生产者消费者；阻塞等待的线程被放入队列。

• 树

• 二叉排序树

左子树上所有结点的值均小于或等于它的根结点的值。右子树上所有结点的值均大于或等于它的根结点的值。左、右子树也分别为二叉排序树。

• 红黑（排序）树

每个节点只有两种颜色：红色和黑色。根节点是黑色的。每个叶子节点（NIL）都是黑色的空节点。从根节点到叶子节点，不会出现两个连续的红色节点。从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

2.3常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划算法

• 遗传算法

3.网络通信协议

3.1Web 请求的一次网络通信历程

web 请求通信

3.2 OSI 模型和TCP/IP 模型

网络模型

3.3网络数据包格式

网络数据包

3.4 TCP/IP模型

• 物理链路层

• 物理层负责数据的物理传输，计算机输入输出的只能是0 1 这样的二进制数据，但是在真正的通信线路里有光纤、电缆、无线各种设备。光信号和电信号，以及无线电磁信号在物理上是完全不同的，如何让这些不同的设备能够理解、处理相同的二进制数据，这就是物理层要解决的问题。

• 链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。

• 网络层

• 网络层IP 协议使得互联网应用根据IP 地址就能访问到目标服务器，请求离开App 后，到达运营服务商的交换机，交换机会根据这个IP 地址进行路由转发，可能中间会经过很多个转发节点，最后数据到达目标服务器。

• 传输层

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

• TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP作为一个比较基础的通讯协议，有很多重要的机制保证了TCP协议的可靠性和强壮性：

• 使用序号，对收到的TCP报文段进行排序和检测重复的数据无错传输

• 使用校验和检测报文段的错误使用确认和计时器来检测和纠正丢包或者延时流量控制

• 避免主机分组发送得过快而使接收方来不及完全收下拥塞控制

• 发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃丢失包的重传

• TCP 建立连接的3次握手过程

• App 先发送SYN=1，Seq=X 的报文，表示请求建立连接，X 是一个随机数；

• 服务器收到这个报文后，应答SYN=1，ACK=X+1，Seq=Y 的报文，表示同意建立连接；

• App 收到这个报文后，检查ACK 的值为自己发送的Seq 值+1，确认建立连接，并发送ACK=Y+1 的报文给服务器；服务器收到这个报文后检查ACK 值为自己发送的Seq值+1，确认建立连接。至此，App 和服务器建立起TCP 连接，就可以进行数据传输了。

• TCP 关闭连接4次挥手

• 客户端向服务器端发送一个FIN，请求关闭数据传输。

• 当服务器接收到客户端的FIN 时，向客户端发送一个ACK，其中ACK 的值等于FIN + SEQ。

• 然后服务器向客户端发送一个FIN，告诉客户端应用程序关闭。

• 当客户端收到服务器端的FIN 是，回复一个ACK 给服务器端。其中ACK 的值等于FIN + SEQ。

• 应用层

• 应用层HTTP 协议

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

• HTTP 请求的7种方法

• Get：只读请求，请求处理过程不应该产生副作用，即web应用不应该因为get 请求而发生任何状态改变。

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

• Post：提交请求。

• Put：上传请求。

• Delete：删除URL 标识的资源。

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

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

• HTTP 响应的5种状态

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

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

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

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

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