第八周学习总结

数据结构与算法

时间复杂度和空间复杂度，用大O（x）表示其复杂程度。P：在多项式时间复杂度内解决的问题，NP:在多项式时间复杂度内验证答案正确与否。

数组和链表，数组适合查找，链表适合增删。hash表查找删除都快，栈先进后出。队列。树：二叉树、红黑树。跳表，相当于建立多级索引，通过查找最外层索引一级一级进入下一级索引，直到找到数据。

常用算法：穷举、递归、贪心、动态规划。遗传算法。

网络通信协议

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

TCP/IP四层模型：应用层、传输层、网络互联层、网络访问（链路）层。

TCP建立连接三次握手和断开连接四次挥手。

非阻塞网络IO

IO操作立即返回，发起线程不会造成阻塞。

系统IO复用方式：select、poll、epoll。select、poll会轮训系统中可读socket，而epoll是将可读socket放入队列，对队列监听，无需轮训。NIO在调用select()方法时依然会被阻塞。

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

SQL--连接器--语法分析器--语义分析与优化器--执行引擎

Mysql:B-树和B+树，聚簇索引：主键和数据行存储在同一个B+树中。非聚簇索引需要根据主键回表查询数据。

数据库事务：ACID 原子性atomicity 隔离性isolation 持久性durability 一致性consistency