架构师训练营第 1 期第 8 周学习总结

本周主要学习了文件与硬盘IO，常用数据结构与算法，以及非阻塞IO。

文件与硬盘IO

机械硬盘速度慢的原因在于磁头的移动，盘片的转速是非常快的。固态硬盘，不需要磁头的移动，所以速度快。B+树，存储了多个数据块。每个磁盘块有数据区间，左边比他小，右边比他大。LSM树是连续读写的。

文件控制块FCB，每个块是4K。Linux用inode文件控制块，inode记录着文件权限，所有者，修改时间和文件大小等文件属性信息。间接索引表指针，每个inode最多存12+256+256*256+256*256*256个数据块，如果每个是4K，单个文件最大不超过70G。

RAID独立硬盘冗余阵列，RAID 0是多块硬盘，离散存相同的数据。RAID 1是两块硬盘，另一块硬盘负责备份。RAID 10是结合RAID 0和RAID 1的特点，多块硬盘离散存数据，而且有备份。RAID 5加入了P校验位，RAID 6加入了P Q两个校验位。

分布式文件系统HDFS，有NameNode和DataNode，每个数据块的大小是64MB。

常见数据结构与算法

1. 时间复杂度

1. n个数据，算法执行语句的次数

2. 多项式时间复杂度，O(1), O(logn), O(n^a)。

3. 非多项式时间复杂度，计算机无法实现的。

2. 空间复杂度

1. 临时占用的空间大小。

2. P问题，多项式时间复杂度内解决的问题。

3. NP问题，多项式时间复杂度内验证答案正确与否。

4. NP?=P

5. NP完全问题。NP-hard问题，也是一个NP问题。

3. 数组

1. 内存中连续的空间，相同的数据类型。

2. 随机快速读写，下标访问时间复杂度是O(1)。

4. 链表

1. 离散的内存空间存数据，增删比数组快很多。

5. 数组链表结合，快速查找和增删

6. hash表

1. 数组存的是指针，指向元素。

1. 链表，拉链法解决数据冲突

2. 长度不一样的问题，也可以解决

3. hash攻击：构造key相同，值不同。覆盖原值，变为长链表，查询缓慢。

7. 栈

1. 线程运行时专有内存称为线程栈，局部变量总是栈顶。不用看x属于f还是g。

8. 队列

1. 先进先出，生产者，消费者。公平锁，谁先来，谁先放在队列。

2. 广度优先搜索BFS。每层都是一个队列。

3. 搜索最短路径，level最小的。通过哪个节点入队列的。

9. 红黑树

1. 二叉排序树(BST-Binary Search Tree)

1. 和有序数组一样，时间复杂度是O(logn)，但BST增删数据更快。

2. 平衡BST

1. 左右子树深度差不超过1

2. 左右子树仍为平衡二叉树

3. 左旋和右旋

1. 左边节点多，右旋

2. 右边节点多，左旋

3. 红黑树

1. 不会出现2个连续红色节点

2. 通过染色和旋转，满足红黑树定义。

3. 最多3次旋转，就重新平衡，时间复杂度O(1)，大量增删时，比BST快。

10. 跳表

1. 增删时，节点可以跳起来，到上一级。

2. 实现简单，但空间复杂度比较大。

1. 对资源无所谓，性能要求高。

2. 人的资源宝贵，计算机资源没那么重要。



经典算法

1. 穷举算法

1. 穷举数目不多的时候。

2. 递归算法

1. 自己调自己，快排

1. terminator终止条件

2. process current，满足要求的

3. drill down，分别往多种可能性递归

4. restore，恢复到原来的位置，如果允许多条路径。

3. 贪心算法

1. 找当前最好的选择，找到局部最优解。

2. 不是全局最优解。但简单，所以速度快。

3. 改进贪心算法

1. 迪杰斯特拉算法，最短路径。

1. 是最优解。

2. 更新邻居节点为最小值

3. 反查到达某个节点最快的节点记录。

4. 动态规划(Programming是网格的意思)

1. 特点

1. 一个模型：重复子问题

2. 三个特征：无后效性，

2. 背包问题

1. 遗传算法

1. 模拟进化过程

1. 选择

1. 适应度函数和控制参数。

2. 交叉

1. 交叉换数据

3. 变异

1. 基因突变染色体

2. 参数

1. 参数编码

3. 步骤

1. 构建染色体(像位运算？)

1. 为1放，0不放。

2. 是非多项式的。

2. 交叉遗传

1. 时间复杂度是根据是否收敛来确定的。

3. 不确定是否全局最优解

1. 性能很好(时间复杂度是常数)，非常不错的结果，比动态规划要快。



非阻塞IO

1. 多线程服务端-客户端

2. 多客户端，多个socket并发处理，每个socket上，创建一个新的线程。

3. BIO, blocking IO, 阻塞IO

4. 线程数有限。

5. socket接收数据，kernel的处理

6. 线程大部分时间都阻塞在这里。

7. 非阻塞方式，处理并发请求，IO操作立即返回。

8. Java NIO

9. Selector，Buffer，SelectableChannel，

10. getInputStream，getOutputStream。

11. server.configureBlocking(false);

12. Server

13. Channel通道

14. ServerChannel。

15. Selector选择器

16. 监控所有的Channel。

17. 不会因为socket缓冲区不足而导致线程阻塞。

18. 方式

19. select

20. poll

21. epoll

22. 系统提供了eventpoll方式。

23. socket很多的时候，性能得到很大提升。

24. server channel，channel A,channel B

25. Buffer缓存

26. 只要写入到Buffer即可。