总结



这周任然是本科内容的速成，用极简的方式回顾了数据结构与算法，以及数据库原理（MySQL为例）。



期间，老师提到一个推荐的学习方法：猜。我同样认为学习的方法比学习和学习到的知识更重要。这就是为什么要上大学的原因。大学是养成自助学习的能力。就如同耶鲁的校长说，耶鲁的学生毕业时竟然学会了某一专业知识是不可想象的，耶鲁的学生毕业生应该掌握获得任意专业知识的方法。猜是一个简练的说法，我想其实是“大胆假设，仔细求证”这个科学家们的常用套路。接触到新鲜事物时，先了解其用途，然后实践，在实践的基础上假设工作原理，这个过程能最大程度地激活已有知识，然后和已知建立联系，最后通过实验检验假设，或是深入实现对比差异，在大脑里建立起深刻的连接。这是一种积极的学习策略，随着学习的深度和广度的扩张，学习加速度也会提升。



数据结构与算法



复杂度理论是研究生课程，前几天才看到文章说C语言之父，图灵奖获得者Daniel的博士论文就是关于复杂度的，在失落52年后重现。



复杂度是对算法效率的衡量，是量级，不是具体的数值。有最优复杂度，平均复杂度，均摊复杂度和最坏复杂度。大O复杂度是最坏复杂度，指最差情况下的量级。



算法理论



时间复杂度与空间复杂度



时间复杂度



时间复杂度是指运算次数的量级。



多项式复杂度



常见有



• 常数复杂度O(1)

• 对数复杂度O(log(n))，O(nlog(n))

• 指数复杂度O(n^a)，a=1时就是线性复杂度



常数，对数和3次方复杂度都是可以实际使用的复杂度。超过3次方的算法基本只有理论意义，无法对大规模数据使用。



非多项式复杂度



常见有



• 幂函数O(a^n), a>1

• 阶乘O(n!)



一般只能用于较小数据集，不是实际可用的算法。



空间复杂度



算法运行期间临时空间的量级。通常不超过O(n)，最好是常数复杂度O(1)。



NP问题



NP完全问题是至今没有解决的数学难题，位于千禧年十大数学问题之一。一个著名的NP完全问题是欧拉图的最短路径遍历问题，我记忆中的学生时代的最佳算法是英国物理学家利用气体分子扩散的布朗运动模拟而得的次优解。



对NP问题的研究主要是评估算法设计的可行性。一般来说，多项式问题（P问题）都是可以找到有效算法的问题，NP问题的最优解算法可能难以实现，一般要考虑近似解，次优解和启发式算法。



算法策略



以前面试必考的算法是各种排序，现在有所升级，所以掌握算法策略才能以不变应万变。常见算法设计策略有以下几种。分治递归可能是最广泛应用的策略，对于最优解问题，大多可以采用动态规划。启发式算法通常也是用于最优解搜索。三种常见启发式算法，遗传算法，退火算法和蚁群算法都是与其他学科交叉的成果。



• 分治递归



• 动态规划



• 贪心算法



• 穷举剪枝



• 启发式算法



数据结构



常见数据结构有表，树和图。表是线性结构，存储上可能连续也可能不连续。树是非线性结构，定义是经典的递归定义。树的特点是没有环。最简单的树是最多两个字节点的二叉树。图的定义一般是顶点和边构成的二元组的集合，分为有向图和无向图。



• 线性表



• 树



• 图



图算法是一类运算与图数据结构上的算法。



• 最短路径算法



• 最小生成树



• 遍历



网络通信



一个经典面试问题就是讲述http请求从浏览器发起到服务器的完整过程，以考察面试者知识的广度。互联网应用的经典过程是



1. 浏览器查询DNS

2. 静态资源到CDN

3. 动态请求到负载均衡

4. 负载均衡到机房反向代理

5. 反向代理到应用集群负载均衡

6. 负载均衡到网关

7. 网关到应用服务器

8. 应用服务器到分布式缓存

9. 应用服务器到数据库

10. 应用服务器到消息队列



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



OSI七层模型TCP/IP四层模型应用层应用层表示层会话层传输层传输层网络层网络层链路层链路层物理层



物理层以上每一层都会封装上一层数据，加入协议头。链路层使用mac地址，每个网卡的mac是全球唯一标识，由国际组织为厂商分配。网络层使用IP地址，传输层定义端口。



负载均衡



L2负载均衡



基于mac地址分发请求，路由过程中改写mac地址。



L3负载均衡



基于IP地址分发请求，路由过程中改写IP地址。



L4负载均衡



基于IP+Port分发请求，路由过程中改写IP或Port。



L7负载均衡



基于应用层协议分发请求，比如HTTP的方法，路径等。



TCP连接的3次握手和4次挥手



3次握手



3次握手是为了确认双方都可以正常收发。



1. Client发送SYN=1，SEQ=X报文，请求建立连接

2. Sever应答SEQ=Y，ACK=X+1报文，同意建立连接

3. Client应答SEQ=Z，ACK=Y+1报文，建立连接



4次挥手



关闭连接时，Sever在接到close请求后，还可以发送剩下的数据，所以需要4次挥手。



1. Client发送FIN=1，SEQ=M报文，请求关闭连接

2. Sever发送ACK=1, SEQ=M+1报文，同意关闭

3. Sever传输数据

4. Sever发送FIN=1，SEQ=N报文，通知关闭

5. Client发送ACK=1，SEQ=N+1报文，确认关闭

6. Client等待2个周期以便所有属于该链接的数据报在网络中清除



内核网络IO处理



1. 网卡接收数据，中断CPU

2. CPU执行中断例程，复制数据到内核空间

3. 复制数据到用户空间

4. 唤醒线程处理数据



在内核中，数据有两个阶段，准备阶段和复制阶段。在准备阶段，线程是否挂起，就是阻塞式和非阻塞式IO的区别，只有异步IO是在数据复制到用户空间后在回调处理线程，其他4中IO依然要执行数据复制，但是复制的时机不同就造成了不同的IO模式，比如reactor在处理线程中复制，而proactor在事件分发线程中复制。



5种IO模式



• 同步阻塞

• 同步非阻塞

• 多路复用

• 事件驱动

• 异步



数据库架构原理



预编译



使用预编译语句PrepareStatement，一方面有性能的提高（MySQL5.7后，因为多核优化的问题，已移除statement cache），另一方面更安全，可以规避SQL注入。



数据库架构



SQL经连接器进入语法解析器，经语义分析与优化器生成执行计划，最后交由执行引擎执行。



连接器



建立连接不是轻量操作，包括分配缓冲区和游标管理，所以通常需要连接池。



语法分析器



SQL语法分析器，生成AST。



语义分析与优化器



遍历AST，分析语义，生成并优化执行计划。



执行引擎



执行计划，计算行，生成结果集。



B树



B-/+树是数据文件存储结构或索引结构。B-树结点包含数据，而B+树只包含主键，不含数据。



索引



一般来说对区分度高的字段建立索引可以提高查询性能，但也不宜过多。索引最好一开始就规划好，不要随便对非空表建索引。



事务



数据库事务具有ACID性质。



• 原子性（Atomicity）：事务不能部分完成，要么全部成功，要么全部不成功。

• 一致性（Consistency）：表约束（关系约束和函数约束）在事务前后都要保持，不能破坏表上和表间的约束条件。

• 隔离性（Isolation）：数据在多个同时进行的事务间的可见性。分四个级别，

• 持久性（Durability）：数据一旦提交，即使崩溃也要保证数据写入。



事务日志



事务的ACID是通过事务日志保证的。一般有redo和undo两种日志。



作业



作业一



方法一



说明



两个链表，对其中一个遍历并放入哈希表，用链表的值做key，保存指向节点的指针（引用）。然后遍历另一个，在哈希表中查找到的第一个节点就是交点，或是遍历到结尾，说明没有交点。



复杂度



空间复杂度为O（max(m, n))，也就是O(n)。遍历连个链表的时间复杂度是O(m+n)，也是O(n)。



方法二



说明



反转两个链表，然后从头开始查找交点，然后再翻转两个链表还原。



复杂度



翻转两个链表要O(1)的额外空间，O(n)的遍历时间复杂度，查找也是O(n)的时间复杂度。最终是O(n)的时间复杂度和O(1)的空间复杂度。