Week 8 总结

磁盘

• 顺序存储好与乱序存储

• B+树,LSM树

• RAID 的分类

* RAID 0 读写性能提升,但是没有安全性

* RAID 1 每个硬盘数据都复制一份,性能又变差

* RAID 10,结合0和1,比较耗资源

* RAID 5,一张磁盘存放校验信息??两块硬盘坏掉就不行

* RAID 6,两块盘坏掉也可以



HDFS 分布式文件系统

• 64Mb一个块

• DataNode 和 NameNode 类似与Linux的文件块和FCB(控制块)



1. 常见数据结构

NP问题

• P问题：多项式时间复杂度内解决的问题

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

• NP hard

• NP complete

• 参考:https://www.jianshu.com/p/dcb0b52f4935



数组

• 空间连续，相同数据类型



链表

• 空间可以不连续

• 数组链表,有点像画正字



1. 红黑树原理

• 二叉排序树,不平衡咋办？

• 平衡二叉排序树，深度之差不超过1

• 为了解决二叉排序树的旋转问题，创造了红黑排序树

• 跳表,空间换时间,在redis中有利用



1. 经典算法

• 穷举算法,通常n*m 时间复杂度

• 递归算法:调用自己,要设置好边界

• 贪心算法:总是作出当前最好选择

• 动态规划

• 遗传算法,没有理解深刻啥意思



1. 网络通信基本原理

• 网关服务器

• 负载均衡服务器有IP 层和数据链路层(MAC地址),修改IP地址必须要经过负载均衡服务器,链路层可以直接返回

• Http 2.0 允许复用同一个tcp连接,提出了流的概念,可能出现队头堵塞,因为有顺序

• QUIC 协议,封装在 UDP 中