Date:  2020/7/29   V1.0

Autor：Jessie



数据结构

时间复杂度和空间复杂度：

时间复杂度：算法执行语句的次数。

O（2^n） 对n数据处理需要2^n次计算。





空间复杂度：算法在运行过程中临时占用的存储空间大小的亮度。

O（n）表示临时存储n个数据。

NP问题

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

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

数据结构

多种数据结构的用法不同，时间复杂度也不同。

数组，用于随机快速查找数据，时间复杂度为O(1).

链表：零散的内存数据，查找数据智能遍历，时间复杂度O（N），每个数据包含下一个指向数据的内存地址指针。但增加、删除方便。

数组链表结合，实现快速查找和增删数据



Hash表，通过计算Key的Hashcode进行取模。快速查找和增删数据。

栈： 栈在线性表上增加了“后进先出”的有限条件。用户线程运行时专有内存，处理函数调用。

队列： 先进先出



   树：

前中后序遍历、二叉树、二叉搜索树、平衡二叉树，更高级一点的有红黑树、B 树、B+ 树等。

       二叉排序树

二叉排序树，左边比根小，右边比根大。并且左右子树都是一个二叉排序树。但是在一个极端情况下，插入序列是有序的，则可能退化成一个链表。





红黑树

 而红黑树，利用规则，保证了树的平衡。

根节点黑色，叶子节点都是黑色空节点。 从根到叶子阶段，不会出现两个连续的红色节点。



增删节点时，会通过染色和旋转，保持红黑树平衡，避免出现不平衡二叉树的现象。也就是降低了树的高度。



跳表：



算法

l  递归算法



l  贪心算法

l  动态规划算法

l  遗传算法解决背包问题

网络通讯协议



一次完整的Web请求的网络通信过程如下：



1.   Web请求通过域名访问，tcp/ip协议，ip通过dns解析为ip地址拿到。

2.   静态(如：图片)资源为cdn的IP地址；动态资源ip（商品、订单列表）需要到负载均衡服务器（数据中心）。

Cdn如果有资源，则直接返回。

Cdn如果资源没有，也会到数据中心的负载均衡服务器拿到。

3.   负载均衡请求分发到反向代理服务器，如果有则返回。如果没有向后发给网关的负载均衡服务器。

4.   网关服务器拿到分发到的请求，调用微服务服务

5.   微服务调用数据库、缓存服务器。

以上流程都基于TCP/IP协议。每一次都是网络连接。

OSI七层模型和TCP/IP协议



网络数据包封装方法



链路层

一个利用数据链路层进行快速负载均衡的例子

就是不修改IP地址，直接修改链路层的MAC地址，将请求直接调度到具体的服务器。



TCP协议

TCP属于可靠协议，利用3次握手建立连接。



TCP关闭连接利用四次握手。



HTTP协议

HTTP请求的7中方法：



客户端发送一个HTTP请求到服务器的请求消息包括以下格式：

请求行（request line）、请求头部（header）、空行和请求数据四个部分组成。





HTTP响应：

HTTP响应也由四个部分组成，分别是：状态行、消息报头、空行和响应正文。

HTTP相应的5种状态。



计算机网络请求处理的方法

l  服务器客户端模式

每次建立Socket，进行阻塞式读写。



l  多线程服务器-客户端模式



l  线程池服务器



阻塞I/O



Socket接收数据，内核处理流程





非阻塞I/O

Java NIO

系统I/O处理方式

数据库架构原理

数据库架构组成

数据库架构由连接器、语法分析器、语义分析与优化器、执行引擎组成。

处理SQL过程如下：

应用程序建立一个长连接（TCP协议），建立数据库连接。拿到sql提交，提交语法分析进行分析生成语法树，进行分析优化， 最后生成执行计划。



连接器

为连接请求分配一块内存空间用于会话上下文管理。这部分非常耗时，连接初始化几百毫秒，用连接池方式复用连接。

语法分析器



为什么PrepareStatement更好

将提交的带占位符的SQL进行预处理，提前生成执行计划。真正执行SQL时，可以直接替换。加快执行的效率，同时还可以防止：SQL注入。类似如下攻击就不会被执行。



B+树—— 数据库索引

这部分参考我的另一篇文章，单独分析数据库索引的数据结构用B+树的原因：

数据库（MySQL）索引的数据结构与树



聚簇索引

数据库记录和索引记录存储在一起。 主键ID和记录行存储在一个B+树



非聚簇索引

叶子节点记录的不是数据行记录，而是主键，通过主键记录找到行记录——回表。





添加索引

添加必要索引可以优化SQL查询性能，

但需要谨慎使用，不要盲目添加索引，尤其在生产环境中。

因为添加索引会重新生成B+树，导致所有操作（包括查询）都会阻塞，为非常耗时的操作。

数据库事务日志

事务日志文件记录更新前的记录，热案后再更新数据库记录，如果过程中某记录更新事变，则事务全部回滚。