第 08 周 优化系统性能 -02 学习总结

用户头像
Jaye
关注
发布于: 2020 年 07 月 29 日

数据结构与算法



  1. 时间复杂度



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



  1. 空间复杂度



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



  1. NP问题



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

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

- NP ?= P

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

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



  1. 数据结构



- 数组



- 特性 :



- 内存创建连续空间

- 必须存放相同的数据



- 随机快速读写数组



- 时间复杂度 : 为O(1)



- 链表



- 特点 :

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

- 每个元素阿斗必须包含一个指向下一个数据元素的内存地址指针

- 查找一个数据只能遍历链表

- 链表中增删数据要比数组性能好的多.

- 时间复杂度 : O(N)



- Hash 表



- 特点

- 快速访问数据

- 快速增删数据

- 时间复杂度

- O(1)

- Hash冲突



- 栈



- 特点 :

- 后进先出

- 时间复杂度 :



- 队列



- 特点 :

- 先进先出

- 应用

- 搜索好友中关系最近的有钱人

- 搜索最短路径



- 树



- 特点

- 多个子树

-

- 应用

- 二叉排序树

- 左子树上所有结点的值均小于或等于它的根结点的值。

- 右子树上所有结点的值均大于或等于它的根结点的值。

- 左、右子树也分别为二叉排序树。

- 时间复杂度

- O(logN)

- 平衡二叉(排序)树

- 从任何一个节点出发,左右子树深度之差的绝对值不超过1。

- 左右子树仍然为平衡二叉树

- 旋转二叉树恢复平衡

- 插入时,最多只需要两次旋转就会重新恢复平衡.删除时,需要维护从被删节点到根节点这条路径上所有节点的平衡性,时间复杂度

O(logN)

- 红黑(排序)树

- 每个节点只有两种颜色:红色和黑色。

- 根节点是黑色的。

- 每个叶子节点(NULL)都是黑色的空节点。

- 从根节点到叶子节点,不会出现两个连续的红色节点

- 从任何一个节点出发,到叶子节点,这条路径上都有相同数目的黑色节点。



- 跳表





  1. 链表与数据对比.



- 频繁增删数据用链表

- 频繁查找多用数组

- 数组链表结合,实现快速査找和快速增删

- 数组做索引,存储链表



  1. 红黑树 VS 平衡二叉树



- 红黑树最多只需3次旋转就会重新达成红黑平衡,时间复杂度o(1)。

- 在大量增删的情况下,红黑树的效率更高。

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



  1. 常用算法



- 穷举算法



- 递归算法



- 贪心算法



- 改进贪心算法-迪杰斯特拉算法(最快路径)



1.找出“最便宣”的节点,即可在最短时间内到达的节点。



2.更新该节点的邻居的开销,检查是否有前往它们的更短路径,如果有,就更新其开销



3.重复这个过程,直到对图中的每个节点都这样做了。



4.计算最终路径



- 动态规划



网络



  1. web请求的一次网络通讯历程





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





  1. HTTP响应的5种状态



- 1x消息一一请求已被服务器接收,继续处理

- 2x成功一一请求已成功被服务器接收、理解、并接受

- 3×重定向一一需要后续操作才能完成这一请求

- 4xx请求错误一一请求含有词法错误或者无法被执行

- 5x服务器错误一一服务器在处理某个正确请求时发生错误



  1. Http协议版本



- HTTP/1.0

- 一次通讯

- HTTP/1.1

- 长链接

- HTTP/2

- 复用TCP

- HTTP/3

- QUIC



  1. 阻塞I/O



- 进行WO操作时,用户线程会一直阻塞,直到读操作或者写操作完成



  1. 非阻塞I/O



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



- 非阻塞read操作



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



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



- 非阻塞wite:

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

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



  1. 系统I/O复用方式



- select

- poll

- epoll



数据库架构原理



  1. 数据库架构

- SQL -> 连接器->语法分析器-->语义分析与优化器-->执行引擎

  1. PrepareStatement预编译

- 提前生成执行计划

- 防止SQL注入攻击

  1. 聚簇索引

- 聚簇索引的数据库记录和索引存储在-起

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

  1. 非聚簇索引

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

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

  1. 要合理使用索引

- alter 消耗时间长

- alter操作期间,全部阻塞



数据库事务



  1. 事务特性ACID

- 原子性( Atomicity!y):事务要么全部完成,要么全部取消。如果事务崩溃,状态回到事

务之前(事务回滚)。

- 隔离性( Isolation):如果2个事务T1和T2同时运行,事务T1和T2最终的结果是相

同的,不管T1和T2谁先结束,隔离性主要依靠锁实现。

- 持久性( Durability):一旦事务提交,不管发生什么(崩溃或者出错),数据要保存在

数据库中。

- 一致性( Consistency):只有合法的数据(依照关系约束和函数约束)才能写入数据库。



  1. 数据库事务日志



用户头像

Jaye

关注

还未添加个人签名 2018.01.23 加入

还未添加个人简介

评论

发布
暂无评论
第08周 优化系统性能-02 学习总结