架构师训练营第八周学习总结

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

数据结构与算法

时间复杂度与空间复杂度

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

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

NP问题

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

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

NP-hard问题:NP问题的解法可以规约到NP-hard问题的解法

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

基本数据结构

数组:内存中一块连续的空间;相同的数据类型;随机快速读写,时间复杂度O(1)

链表:零散的内存空间存储数据;每个数据元素包含一个指向下一个数据元素的内存地址指针;查找需要遍历链表,时间复杂度O(N),但是链表中增删数据要比数组性能好的多。数组链表结合,实现快速查找和快速增删

Hash表

数组和链表都被称为线性表,先进先出为队列,后进先出为栈。

树:二叉排序树、平衡二叉排序树、红黑(排序)树

红黑树VS平衡二叉树:

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

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

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

跳表

常用算法

常用算法有:穷举算法、递归算法、贪心算法和动态规划

遗传算法

网络通信协议

osi七层模型和tcp/ip四层模型

网络数据包格式

传输层:tcp协议

tcp建立连接的3次握手

tcp关闭连接的4次握手

应用层的 http协议

非阻塞网络I/O

阻塞IO

非阻塞I/O

Java NIO(NEW I/O)

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

数据库架构原理与性能优化

优化方式:PrepareStatement 预编译

数据库架构:

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

B树和B+树

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

非聚簇索引:在叶子节点记录的不是数据行记录,而是聚簇索引,也就是主键,通过非聚簇索引找到主键索引,再通过主键索引找到行记录的过程也被称作回表

添加必要的索引优化SQL查询性能

谨慎使用索引

1.不要盲目添加索引,尤其在生产环境

2.删除不用的索引,避免不必要的增删开销

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

数据库事务,以及经验之谈谨慎使用分布式数据库事务,使用数据库手动补偿即手动回滚数据库。



用户头像

fenix

关注

还未添加个人签名 2018.03.02 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第八周学习总结