架构师训练营 W8 学习总结

时间复杂度与空间复杂度



时间复杂度不是算法执行的时间，而是算法执行语句执行的次数



空间复杂度表示算法在运行过程中临时占用存储空间的量度



NP问题



P 问题： 多项式时间复杂度



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



NP - hard 问题：比 NP 问题更难的问题



NP 完全问题：是 NP，也是 NP-hard



数组



内存中连续空间



数据类型相同



链表



零散内存空间



Hash表



快速访问， 删除



Stack



后进先出



队列



先进先出



常用算法



• 穷举

• 递归

• 贪心

• DP

树



二叉搜索树



平衡二叉树



红黑树



跳表



网络





• 物理层

• 数据链路层

• 网络层

• 传输层



TCP 3 次握手





• TCP 4 次挥手





• 应用层



HTTP 协议 为全球用户提供服务。

HTTP 版本

• HTTP/1.0 每次请求资源后都会关闭连接，并发大的时候会导致频繁创建、关闭 TCP 连接

• HTTP/1.1 默认启用长连接。同一个 TCP连接顺序发送多个请求，Client 可以不用等上次请求返回结果就可发送下一个请求。但是服务器需要按照客户端请求的顺序进行响应，是一种半双工模式

• HTTP/2 也是服用 TCP 连接。但是客户端发送多个请求和服务端给出多个响应的顺序不受限制。



非阻塞 IO



IO 操作立刻返回，发起线程不会阻塞等待



系统 IO 复用的方式：select, poll, epoll







数据库架构与性能优化



架构：



PrepareStatement

会预先提交带占位符的 SQL 到数据库进行预处理，提前生成执行计划，当给定占位符参数，真正执行 SQL 的时候，执行引擎可以直接执行，效率更高。此外，还可以防止 SQL 注入攻击。



聚簇索引

数据库数据和索引存储在一起。



非聚簇索引

叶子结点记录的不是数据行记录，而是索引。



谨慎使用索引

• 添加索引的 alter 会消耗较长时间（分钟级），再次期间 增删改 操作全部阻塞，因为连接不能释放，其实读也被阻塞

• 删除不必要的索引，避免不必要的开销

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



数据库事务

ACID

A：原子性。一个事务中操作，要么都成功，要么都失败

C：一致性。只有合法的数据（符合约束）才能写入数据库

I：隔离性。2 个事务同时运行，最终结果是一样的，不管谁先结束

D：持久性。事务一旦提交，无论发生什么，结果都要保存在数据库中



数据库事务日志



进行数据库事务操作时，事务日志文件会记录更新前的数据记录，然后再更新数据库中的记录。如果所有操作成功，事务正常结束。如果某条操作失败，整个事务回滚，已经更新的记录根据事务日志中记录的数据进行恢复.