架构师训练营 1 期 -- 第八周笔记

机械硬盘读取数据时，需要磁带转到指定的扇区，然后移动磁头进行读取。磁头移动的速度比较慢，所以如果数据不是连续存储的，那么读取速度就会变慢。

虽然固态硬盘能极大提高磁盘存储效率，但是连续读取速度仍然比随机读取要快。

操作系统存储文件时，是以块为单位的，通常文件的元数据存储在文件控制块中。在 Linux 系统中，文件控制块包含了文件名，大小，权限，所有者，时间，以及数据块等信息。

为了提高磁盘的读写速度，人们采用了 RAID 技术，就是将数据同时写入多块磁盘，并冗余存储，这样既可以提高读写性能，又能做安全备份。比较常用的是 RAID5 和 RAID6，既提高好的读写性能，又提高了数据安全性。

对于分布式文件存储系统 HDFS，其设计原理和磁盘存储原理是一样的，HDFS 中包含 Name 节点和数据节点。Name 节点负责存储文件元数据，并控制将文件写往哪个数据节点。而数据节点则负责数据的读写，并负责数据的复制。客户端需要读取或写入数据时，先和 Name 节点通信，确定将数据写入哪个节点，然后再和数据节点通信，进行数据的读写。HDFS 默认数据会存储 3 份，当数据节点宕机时，Name 节点会给其它数据节点发送指令，将宕机节点的数据通过其它数据节点进行复制，确保数据一直保留 3 份。

时间复杂度是指程序在运行过程中需要执行的次数。通常用 O 表示，如 O(n)，O(1)，O(logn)等。

空间复杂度是指在程序运行过程中需要使用的临时空间。

数组是连续的存储结构，并且存储的类型必须相同。特点是查找快，插入删除慢。

链表可以是不连续的存储空间，并且类型也不做要求。特点是查找慢，插入删除块。

可以将二者结合起来使用，这就是 hash 表的应用。Hash 表是一个数组，存储时，通过 key 找到 hash 值，然后对数组长度取模，得到数组下标，将元素存储到数组对应的位置。实际上元素存储是以链表方式进行存储的，当有多个数据存储到相同的数组下标时，将存储的数据添加到链表中。

栈是一种后进先出的数据结构，可以使用数组，也可以使用链表来实现。在 JVM 的函数调用中，就是使用栈来实现的，将需要访问的数据压入栈顶，执行相关操作，再出栈。

队列是先进先出的数据结构，有很多应用场景。有意思的是老师说可以用队列来查找距离身边最近的有钱人以及查找最短路径。