数据结构和算法

时间复杂度和空间复杂度

时间复杂度并不是计算程序具体运行时间，而是算法执行语句的次数空间复杂度程序运行期间占用的存储

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

基本数据结构

数组

内存中连续的空间存放相同的类型随机快速读写

链表

每个元素包含指向下个元素的指针

链表中的数据查找只能遍历

链表中增删数据性能更好

hash表

既能快速访问数据，又能快速增删数据

栈

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

栈就是在线性表的基础上加了操作限制条件：后进先出

队列

先进先出

树

• 二叉排序树

• 平衡二叉排序树

• 红黑排序树：解决平衡二叉树在平衡过程中的时间复杂度问题

红黑树最多只需要3次旋转就能达到红黑平衡，在大量增删的情况下效率更高，但是平衡性不如平衡二叉树

跳表

常用算法

穷举递归贪心动态规划



网络通信协议

网络模型

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





网络数据包格式





物理层

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

链路层

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

网络层

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

传输层（TCP协议）

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

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

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

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

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

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

应用层HTTP协议

Get:只读请求,请求处理过程不应该产生副作用,即web应用不应该因为get请求而发生任何状态改变Head:和get方法一样,但是只返回响应头Post:提交请求。Put:上传请求。Delete:删除URL标识的资源。race:回显服务器收到的请求,用以测试或者诊断。Options:请求服务器返回支持的所有HTTP请求方法,测试服务器是否正常。

非阻塞IO

阻塞IO:进行IO操作时用户线程会一直阻塞,直到读操作或者写操作完成.

非阻塞IO:IO操作立即返回,发起线程不会阻塞等待。

IO复用：select, poll, epoll

数据库架构原理

数据库架构





连接器

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

语法分析器

语义分析与优化器

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

B-树与B+树

非聚簇索引

非聚簇索引在叶子节点记录的就不是数据行记录,而是聚族索引,也就是主鍵通过非聚族索引找到主键索引,再通过主键索引找到行记录的过程也被称作回表。

事务

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

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

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

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