总结

网络

常见网络模型有OSI七层模型，TCP/IP四层模型，两种模型的对应关系以及每层的作用如下图所示：

比如我们常见的HTTP协议工作在应用层，如TCP、UDP协议工作在传输层，如IP、ICMP等协议工作在网络层。

• 物理层：物理层负责数据的物理传输。因为计算机只识别01这样的二进制数据，物理层要保证这些二进制数据能在不同的物理媒介(如光纤、电缆、无线设备)上传输。

• 数据链路层：将数据封装成帧，帧会有大小，也会进行数据校验，在帧头中会增加机器的mac地址，保证数据能够送达正确的机器

• 网络层：根据IP地址访问到目标服务器，主要是路由功能

• 传输层：提供可靠的端到端的网络数据流服务

• 应用层：包括HTTP、HTTPS、FTP、SMTP等等，包括RPC框架的dubbo协议等等，大部分涉及通讯的框架都会定义自己的协议。

TCP的三次握手已经四次挥手过程如下图所示：

我们经常会在服务器上看到CLOSE_WAIT或者FIN_WATI1、FIN_WATI2、TIME_WAIT，搞懂了TCP的断开过程就可以明白哪一个环节出现问题了。

HTTP协议是使用最广的协议，下面看一下几种HTTP协议

• HTTP1.0：是使用比较多的，支持传输文字、图片、视频、二进制文件。缺点是连接无法复用，会频繁的创建连接。

• HTTP1.1：增加缓存处理，默认启用了长连接模式，但任一时间点每个连接只能执行一次请求/响应，所以需要过去多个资源也只能开启多个TCP连接。

• HTTP2.0：多路复用技术，多个HTTP请求并发的复用同一个TCP连接，解决了单个TCP连接使用效率低的问题，但TCP队头阻塞的问题并没有解决。多个请求是在同一个TCP连接中，如果前面的请求没有处理完，后面的请求也无法处理

• HTTP3.0：不使用TCP作为传输层，使用QUIC，QUIC是独立的，一个流的丢包不会影响其他流。

数据库

大体来说，MySQL 可以分为 Server 层和存储引擎层两部分。Server 层包括连接器、查询缓存、分析器、优化器、执行器。

• 连接器：连接器负责跟客户端建立连接、获取权限、维持和管理连接。

• 分析器：词法分析是MySQL 需要识别出SQL的字符串分别是什么，代表什么。语法分析是根据词法分析的结果，语法分析器会根据语法规则，判断你输入的这个 SQL 语句是否满足 MySQL 语法。

• 优化器：优化器是在表里面有多个索引的时候，决定使用哪个索引；或者在一个语句有多表关联（join）的时候，决定各个表的连接顺序。

• 执行器：执行语句，根据引擎的不同，调用不同的引擎执行。

为什么使用PrepareStatement？

• PrepareStatement会预先提交带占位符的SQL到数据库进行预处理，提前生成执行计划，当给定占位符参数，真正执行SQL的时候，执行引擎可以直接执行，效率更高。

• PrepareStatement可以防止SQL注入

索引

• 聚簇索引：聚簇索引的数据库记录和索引存储在一起，MYSQL的主键是聚簇索引。

• 非聚簇索引：非聚簇索引的叶子节点不是数据记录，而是主键，通过非聚簇索引找到主键索引，再通过主键索引找到行记录的过程称为回表。

优化

• 可以根据explain执行计划来看SQL有没有用到索引，可以找到需要优化的索引。但是不要盲目的添加索引，尤其是在生产环境中，因为添加索引比较耗时

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

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

数据结构

时间复杂度：并不是程序具体运行的时间，而是算法执行语句的次数，一般我们用大O表示法；空间复杂度：一个算法在运行过程中临时占用存储空间大小的量度。

P：能在多项式时间复杂度内解决的问题；

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

我们常见的数据结构：

• 数组：是一组线性表的数据结构，它用一组连续的内存空间，来存储一组相同数据类型的数据

• 链表：使用零散的内存空间来存储数据，通过指针将这些内存空间串联起来。链表分为单向链表、双向链表、循环链表

• 栈：栈是一种操作受限的线性表，满足后进先出，先进后出的特性，只能在栈顶增加和删除数据。可以基于数组或者链表实现

• 队列：队列也是一种操作受限的线性表数据结构，满足先进先出，后进后出，可以在队头出队，在队尾入队。也可以基于数组或者链表实现

• 哈希表：基于数组实现，用散列函数求出数据的散列值，然后根据数组的长度取模后映射到数组的下标，然后数据存储在数组中对应下标的位置。如果不同的数据求出的散列值一样，会出现散列冲突。可以采用链表法、开放地址法、重hash来解决冲突。哈希表支持非常快速的访问数据以及删除数据

• 树：树是被称为结点的实体的集合。结点通过边连接。每个结点都包含值或数据，并且每结节点可能有也可能没有子结点

• 二叉排序树：左子树上所有节点的值均小于或等于它的根节点的值，右子树上所有节点的值均大于或等于它的根节点的值，左右子树也分别是二叉排序树。

• 平衡二叉树：从任何一个节点出发，左右子树的深度之差的绝对值不超过1

• 红黑树：满足下面几个条件，1、节点是红色或黑色；2、根节点是黑色；3、每个叶子节点都是黑色的空节点（NIL节点）；4、每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)；5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

• 跳表：给链表加多级索引的结构，就是跳表类似于下图：

我们常见的算法及算法思想：

• 二分查找：二分查找针对的是有序的数据集合，每次都是通过跟区间的中间元素进行对比，将待查找区间缩小一半，直到找到要查找的元素或者区间被缩小为0

• 排序：常见的冒泡排序、选择排序、插入排序、快速排序、归并排序以及桶排序、计数排序、基数排序

• 递归：满足下列条件的问题适合用递归来解决：1. 一个问题的解可以分解为几个子问题的解；2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样；3. 存在递归终止条件

• 贪心算法：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

• 回溯算法：从一组可能的解中，选择出一个满足要求的解。

• 分治算法：就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

• 动态规划：通过找到合适的角度，将所求解的目标值在某几个维度上展开，将一个大问题拆解为若干小问题，小问题的最优解，寻找大问题的最优解。