数据结构与算法、网络协议、数据库架构总结

发布于: 2020 年 07 月 29 日



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+树,导致所有操作(包括查询)都会阻塞,为非常耗时的操作。

 

数据库事务日志

 

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

 

发布于: 2020 年 07 月 29 日 阅读数: 41
用户头像

还未添加个人签名 2018.08.21 加入

码过代码、做过产品;擅长码字、演讲、认真做事之人。

评论

发布
暂无评论
数据结构与算法、网络协议、数据库架构总结