架构师训练营 第八周 总结

用户头像
Poplar
关注
发布于: 20 小时前

算法

评估一个算法的好坏需要用到大O复杂度,算法复杂度有时间复杂度和空间复杂度,评估的方式是随着输入变量的变化整个算法需要执行的次数和所需要的空间与输入变量n的关系。

常用的数据结构有数组、链表、hash、栈、队列。数组的优势在随机查找时间复杂度,链表的优势在插入和删除,hash优势在通过一个key去获取value,栈是后进先出,队列是先进后出。

常用的算法有穷举算法、递归算法、贪心算法、动态规划。穷举就是列举所有的可能,从中获取需要的结果。递归是方法调用自己,但是一定记得有退出条件,否则会导致栈溢出。贪心算法是每次执行的时候都选择在当前情况下的最优解。动态规划是结合历史去选择最优解。

因为插入和删除的问题,有可能会使二叉查找树退化成链表,为了解决这个问题产生了平衡的二叉搜索树,平衡二叉树的查找时间复杂度是O(logn),平衡二叉树的插入时间复杂度还好,旋转几次就行,但是删除最坏情况下时间复杂度为O(logn)。为了解决平衡二叉搜索树的删除的复杂度,出现了红黑树,红黑树最多只需要3次旋转就会重新达成红黑平衡,时间复杂度是O(1),在大量增删的情况下红黑树的效率更高,但是它的平衡性不如平衡二叉树,所以查询效率要差一些。



网络

TCP协议为了保证数据完整性,有三次握手来建立连接,有四次挥手来断开连接,而且TCP协议会使用序号对接受到的报文段进行排序和重复检测,有无错传输中校验和检测报文段的错误,有使用确认和计时器来检测和就整丢包或者延时,有流量控制避免接收方来不及完全接收,有拥塞控制。

http协议是应用层协议,它依赖于tcp协议。

http协议的keep-alive对http连接进行复用,但同一时间只能处理一个请求/响应交换。

一个http协议的数据包包含http请求头和请求体,TCP协议头包含端口,IP协议头包含服务器IP,链路层协议头包含服务器MAC地址。

非阻塞I/O有三种实现select、poll、epoll。select和poll差不多,在线程被激活的时候需要遍历所有socket,而epoll维护了事件列表,在线程被激活时只需要处理有事件的socket。



数据库

PrepareStatement预编译会对sql预编译,它可以防止sql注入攻击,因为PrepareStatement会预先提交带占位符的语句进行预处理,提前生成执行计划,当给定占位符参数去执行sql的时候,参数只是一个普通的字符串,不会被当成sql语句执行。同样的,由于预编译了,不用每次执行这个sql语句的时候都执行一遍,PrepareStatement预编译有更好的性能。

mysql的索引是B+树,B+树是文件系统的排序查找树。

对于聚簇索引来说,索引的文件实际上是B+树的数据文件,所有的数据都在叶子结点上。非聚簇索引的B+树的叶子节点放着的是对应的聚簇索引,非聚簇索引查找的时候会先找到对应的聚簇索引,再去聚簇索引上找数据。

对已经存在数据的表添加索引会消耗大量时间,因为需要根据数据去构建B+树,在添加索引过程中,增删改操作会被阻塞,由于增删改操作被阻塞,大量的数据库连接被占用,从而会导致查操作获取不到连接,导致应用长时间不可用。

不要随便建立索引,因为索引会增加插入和删除的代价。



用户头像

Poplar

关注

还未添加个人签名 2018.04.23 加入

还未添加个人简介

评论

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