架构师训练营 week08 学习总结

时间复杂度与空间复杂度

NP 问题、P、NP-hard、NP 完全问题



数组：内存连续、数据类型相同、随机快速读写、根据数组下标访问数据时间复杂度为 O(1)

链表：可以使用零散的内存空间存储数据，查找复杂度是 O(N),增删数据性能好

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

hash 表：hash 表 key 冲突，使用链表存储数据



栈：后进先出

队列：先进先出

用队列搜索好友关系中最有钱的人、用队列搜索最短路径



树：二叉排序树、不平衡的二叉(排序)树、平衡二叉(排序)树、红黑(排序)树

红黑树 VS 平衡二叉树：大量增删情况下，红黑树性能更高，查找效率稍微差一些

跳表



常用算法：穷举算法、递归算法、贪心算法、迪杰斯特拉算法(改进贪心算法)、动态规划、遗传算法



OSI 七层模型：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

TCP/IP 四层模型：网络访问层、网络互联层、传输层、应用层



网络数据包格式：链路层协议头(mac 地址) -> IP 协议头(IP) -> TCP 协议头(端口) -> HTTP 协议头(方法、path)



TCP 协议：面向连接的、可靠的、基于字节流的传输层协议

使用序号，对收到的 TCP 报文进行排序和检测重复的数据

无错传输：使用校验和检测报文段的错误

使用确认和计时器来检测和纠正丢包或者延时

流量控制，避免主机分组发送过快而使接收方来不及完全收下

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

丢失包的重传



TCP3 次握手：

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

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

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



TCP 关闭连接 4 次挥手：

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

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

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

4、当客户端收到服务端的 FIN 时，回复一个 ACK 给服务器端。其中 ACK 的值等于 FIN+Seq。



HTPP 的七种方法和五种状态



HTTP 协议版本：

HTTP/1.0,客户端请求到资源后会关闭连接，频繁三次握手、四次挥手很耗性能

HTTP/1.1，默认启用长连接模式，客户端可以使用一个长连接顺序发送多个请求。引入了管道机制，客户端可以不用等上一个请求的响应结果就可以发送下一个请求，但是服务端也是按照客户端发送顺序进行响应的，可以理解为半双工模式

HTTP/2.0,依然遵循请求响应模式，但客户端发送多个请求和服务端给出多个响应的顺序不受限制，这样既避免了队头阻塞，又能更快获取响应



客户端与服务端通过 socket 进行通信，一个连接一个 socket，一个 socket 可以采用一个线程或者线程池进行业务处理



BIO: 进行 I/O 操作时，用户线程会一致阻塞，知道读操作或写操作完成

NIO(非阻塞 IO)：I/O 操作立即返回，发起线程不会阻塞等待

系统 IO 复用方式：select、poll、epoll

epoll 性能最好，poll 其次



数据库 preppareStatement 预编译，提前生产查询计划，性能更好，还能防止 sql 注入

数据库连接池：初始化的时候建立一些数据库连接放在连接池里，处理 sql 的时候就不需要花时间建立连接了

数据库语法分析器、语义分析与优化器、执行计划

B-树与 B+树

聚簇索引

添加索引可以优化查询性能，但是也不要盲目添加索引，添加索引的 alter 会消耗较长的时间，阻塞 DML

数据库事务：原子性、隔离性、持久性、一致性