架构师培训 -08 总结 数据结构算法,网络通信协议,非阻塞网络 I/O,数据库原理

用户头像
刘敏
关注
发布于: 2020 年 07 月 30 日

1.数据结构与算法

数据结构与算法是为了解决让代码如何运行的更快,如何更省存储空间的问题。在数据结构与算法中通过时间、空间复杂度两个维度来衡量代码是否运行的更快,更省存储空间。用大O表示复杂度。

  • 时间复杂度

并不是程序具体的运行时间,而是算法执行语句的次数。

O(2^n)表示对n数据处理需要进行2^n次计算。

  • 空间复杂度

一个算法在运行过程中临时占用存储空间大小的度量。

O(n)表示需要临时存储n个数据。

NP问题

  • P:能在多项式时间复杂度内解决问题。

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

  • NP-hard:比NP问题更难的问题(NP问题的解法可以规约到NP-hard问题的解决)。

  • NP完全问题:是一个NP-hard问题,也是一个NP问题。



1.1常用数据结构

  • 数组

创建数组必须要内存中一块连续的空间,且必须存放相同的数据类型。

特点:随机快速读写,根据数组的下标访问数据(直接根据内存地址偏移方式获取),读的时间复杂度为O(1),如果不是在数组末尾添加,删除数据,就会有移动数据操作。

  • 链表

可以使用零散的内存空间存储数据。

特点:查找数据,只能遍历链表,查找时间复制度O(n).与数组相比读性能低,添加,删除操作不需要移动其他元素。

  • hash表

既然快速读数据,也能快速删数据。

在线性表(数组和链表)基础上添加了“先进后出”的操作限制。

  • 队列

在线性表(数组和链表)基础上添加了“先进先出”的操作限制。

应用场景:搜索好友关系最近的有钱人、搜索最近路径。

常见的有不平衡二叉树,平衡二叉树,红黑树等。

平衡二叉树VS红黑树

a.红黑树最多需要3次旋转就会重新达到红黑平衡,时间复杂度O(1).

b.大量删除时,红黑树效率更高。

c.红黑树的平衡性不如平衡二叉树,查找效率要差一些。

  • 跳表



1.2常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划

  • 遗传算法

2.网络通信协议

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

2.2网络数据包格式



2.3TCP协议(传输层)

TCP建立连接的3次握手过程

TCP关闭连接4次挥手

2.4http协议

http请求7种方法

http响应5种状态

http协议版本



3.非阻塞网络 I/O

I/O的阻塞与非阻塞都上针对一个线程而言的。

  • BIO(Blocking I/O 阻塞I/O)

进行I/O操作时,用户线程会一直阻塞,知道读操作或写操作完成。



  • 非阻塞I/O(Non-Blocking I/O)

I/O操作立即返回,发起线程不会阻塞等待。

非阻塞read操作:

Socket接收缓冲区有数据,读n个(不保证数据被读完整,因此可能要读多次)

Socket接收缓冲区没数据,则返回失败(不会等待)。

非阻塞write操作:

Socket发送缓冲区满,返回失败(不会等待)

Socket发送缓冲区没满,写n个数据(不保证一次性全部写完,因此可能需要些多次)。



  • Java NIO(New I/O)

NIO与传统I/O之间第一个最大的区别是,IO是面向流的,NIO是面向缓冲区的。

四个主要对象:Selector,Buffer,Channel,SelectionKey。





系统I/O复用方式:select,poll,epoll

select(poll)管理下的read过程

epoll管理下的read过程



4.数据库原理



4.1数据库架构



mysql数据库架构图(引用林晓斌的图)

  • 连接器

数据库连接器为每个连接请求分配一块专用的内存空间用于上下文管理。建立连接对数据库而言相对比较重,需要花费一定的时间,因此应用程序启动的时候,通常会初始化建立一些数据库连接方在连接池里,这样当处理外部请求执行SQL操作的时候,就不需要花费建立连接的时间了。

  • 语法分析器

通过分析SQL生成语法树,并校验SQL语法问题。

  • 语义分析与优化器

将各种复杂嵌套的SQL进行语义等价转化,等到有限的几种关系代数计算结构,并利用索引信息进一步进行优化。

  • 执行计划



4.2索引

聚簇索引:数据库记录和索引存储在一起。

mysql数据库的主键就是聚簇索引,主键ID和所在的记录行存储在一个B+树中。

非聚簇索引:在叶子结点记录的就不是数据行记录,而是聚簇索引,也就是主键。

通过非聚簇索引找到主键,在通过主键索引找到行记录的过程被称作回表。

在MYSQL中当某个查询并发量非常大,可以通过建立复合索引来进行优化,直接通过复合索引获取需要查询的结果,减少回表的操作。



使用索引的注意点:

4.3数据库事务



用户头像

刘敏

关注

还未添加个人签名 2018.04.25 加入

还未添加个人简介

评论

发布
暂无评论
架构师培训 -08总结 数据结构算法,网络通信协议,非阻塞网络 I/O,数据库原理