算法

复杂度

• 时间复杂度: 算法执行语句的次数

• 空间复杂度: 算法运行过程中临时占用的存储空间大小

• 样例



NP问题

• P问题

• NP问题

• NP-hard



递归算法

• 时间复杂度: n * log(n)

• 空间复杂度: log(n)



贪心算法

• 迪杰斯特拉算法(最快路径)



动态规划算法

将所求的目标值在几个维度展开，将大问题拆解为若干小问题，小问题的最优解，寻找大问题的最优解。



遗传算法

• 基因编码与染色体(随机)

• 适应函数与控制参数

• 选择算法

• 交叉遗传/可变异 (随机)



数据结构

数组

• 内存空间连续

• 存储数据类型相同

• 随机快速访问（依据下标访问）



链表

• 内存空间不连续

• 包含自身元素和其他地址指针

• 查询数据需要遍历，时间复杂度O(N)

• 增删时间复杂度O(1)



HASH表

通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。



栈

后进先出



队列

先进先出



树

• 二叉树

• 排序二叉树

• 平衡二叉树

• 红黑树



跳表

类似可二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。



网络通信协议

web请求一次的网络通信历程



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



网络数据包格式



tcp通信

• 连接:三次握手

• 关闭:四次挥手



HTTP 请求方法

• GET:只读请求

• HEAD:与GET相同，但仅返回响应头

• POST:提交请求

• PUT:上传请求

• DELETE:删除URL标识的资源

• TRACE:回显服务器的请求，用以测试或诊断

• OPTIONS:请求服务器返回所有支持的HTTP请求方法



HTTP 响应状态

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

• 2xx成功:请求已成功被服务器接收

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

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

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



HTTP 版本

• HTTP1.0

短连接

无记录

• HTTP1.1

持久连接

缓存处理

带宽优化及网络连接的使用

错误通知的管理

消息在网络中的发送

互联网地址的维护

安全性及完整性

• HTTP2.0

多路复用

二进制分帧

首部压缩

服务端推送



阻塞与非阻塞

阻塞

如果请求数据结果不能立即获取，则等待

非阻塞

如果请求数据结果不能立即获取, 则返回错误码



同步

同一流程在同一线程中处理

异步

同一流程在不同线程中处理



select/poll

kernel内核就会轮询检查所有select/poll负责的文件描述符fd，当找到其中那个的数据准备好了文件描述符，会返回给select/poll，select/poll通知系统调用，将数据从kernel内核复制到进程缓冲区(用户空间)。

select的几大缺点：

（1）每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大

（2）同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大

（3）select支持的文件描述符数量太小了，默认是1024



epoll

epoll与select/poll流程相反，无需主动查询，由中断产生假如列表中



数据库架构原理与性能优化



preparestatement预编译

• 效率高

• 防止SQL注入



数据库架构

索引



• 聚簇索引(B+树)

• 非聚簇索引(B+树)



• 删除无用索引，避免增加增删开销

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



事务ACID

• Atomicity 原子性

一个事务必须被视为一个不可分割的最小工作单元。

• Consistency 一致性

数据库总是从一个一致性的状态转换到另外一个一致性的状态。

• Isolation 隔离性

通常来说，一个事务所做的修改在最终提交之前，对其他事物是不可见的。

• Durability 持久性

一旦事务提交，则其所做的修改就会永久保存到数据库中。



事务日志

进行事务操作是，先记录更新前的数据记录，在更新数据库中的记录。如果全成功，事务结束；如果失败，整个事务回滚到之前的状态。

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

• TransID: 产生操作的事务ID

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

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

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

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