数据结构、网络、数据库总结

1. 数据结构与算法



1. 网络

• OSI七层模型和TCP/I P四层模型



• 物理层

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

• 链路层

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

链路层会定义帧的大小，这个大小也被称为最大传输单元。像日丁丁尸要在传输的数据上添加一个HTTP头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接受者的MAC地址。MAC地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。

• 网络层

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

网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的IP数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个IP头，主要包括的就是发送者和接受者的IP地址。

• 传输层（TCP协议）

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

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

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

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

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

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

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

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





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

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和服务器建立起丁CP连接，就可以进行数据传输了。



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

HTTP请求的7种方法

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

态改变。

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

Post:提交请求。

Put:上传请求。

Delete:删除URL标识的资源。

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

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

HTTP响应的5种状态

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

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

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

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

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



• 网络数据打包格式



Socket接收数据，系统内核的处理过程



• 非阻塞网络IO

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

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

非阻塞read操作

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

Socket接收缓冲区没数据, 则返回失败(不会等待)。

非阻塞write

Socket发送缓冲区满，返回失败(不会等待)。

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



系统ＩＯ复用方式:select, poll, epoll

select下读过程（轮询数据是否准备完成）

poll 下读过程（轮询Socket）

epoll 下读过程（事件列表唤醒处理）



1. 数据库架构原理和性能优化

• 数据库架构

数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对数据库而言相对比较重，需要花费一定的时间，因此应用程序启动的时候，通常会初始化建立一些数据库连接放在连接池里，这样当处理外部请求执行SQL操作的时候，就不需要花费时间建立连接了。

语法分析器

语义分析与优化器就是要将各种复杂嵌套的SQL进行语义等价转化，得到有限几种关系代数计算结构，并利用索引等信息进一步进行优化。

执行计划

Key：索引类型，NULL无索引

Rows：需要处理的行数

Possible_ keys：潜在可以利用的索引



事务特性ACID

原子性(Atomicity ):事务要么全部完成，要么全部取消。如果事务崩溃，状态回到事务之前(事务回滚)。

隔离性(Isolation ):如果2个事务T1和T2同时运行，事务T1和T2最终的结果是相同的，不管T1和T2谁先结束，隔离性主要依靠锁实现。

持久性(Durability):一旦事务提交，不管发生什么(崩溃或者出错)，数据要保存在数据库中。

一致性(Consistency ):只有合法的数据(依照关系约束和函数约束)才能写入数据库。



数据库事物日志

进行事务操作时，事务日志文件会记录更新前的数据记录，然后再更新数据库中的记录，如果全部记录都更新成功，那么事务正常结束，如果过程中某条记录更新失败，那么整个事务全部回滚，已经更新的记录根据事务日志中记录的数据进行恢复，这样全部数据都恢复到事务提交前的状态，仍然保持数据一致性。





LSN:一个按时间顺序分配的唯一事务记录日志序列号

TransID:产生操作的事务ID

PageID:被修改的数据在磁盘上的位置。

PrevLSN:同一个事务产生的上一条日志记录的指针。

UNDO:取消本次操作的方法，按照此方法回滚。

REDO:重复本次操作的方法。

性能优化

1）PrepareStatement会预先提交带占位符的SQL到数据库进行预处理，提前生成执行计

划，当给定占位符参数，真正执行SQL的时候，执行引擎可以直接执行，效率更好一点。

PrepareStatement可以防止SQL注入攻击。



2）添加索引优化SQL性能

在几百万行的数据库中查找一个条记录，如果没有索引，就需要全表扫描，检索所有的

行记录，才能找到需要的记录。

慎用索引

不要盲目添加索引，尤其在生产环境中

添加索弓}的alter操作会消耗较长的时间(分钟级)

Alter操作期间，所有数据库的增删改操作全部阻塞，对应用而言，因为连接不能释放，事实

上，查询也被阻塞。

删除不用的索引，避免不必要的增删开销

使用更小的数据类型创建索引

int 4字节bigint 8字节，Timestamp 4字节Datetime 8字节