【架构师训练营 1 期】第八周学习总结

了解机械硬盘构造原理：

随机读写效率很低，移动磁头耗时，性能主要取决于数据在磁道上是否是连续的。

了解固态银盘构造原理：

通过存储颗粒来处理数据，避免机械的耗时操作，性能也会受到是否连续读写所影响。

学习数据库索引 B+树的查找原理：

通过遍历树的方式，其查找性能受离散存储所影响。

了解 LSB 树：以日志的方式保持顺序读写。

了解文件控制块：

操作系统的文件管理方式：以块来划分，文件所占用的块的信息存放在文件控制块里。

了解如何提高硬盘上的文件读写速度：

通过冗余的 RAID 磁盘阵列，进行同时读/写。RAID 性能好安全性差。RAID 安全性高性能差。RAID10 结合 RAID0 和 RAID1，同时保证性能和高可用，但磁盘浪费严重。RAID5 对多个数据分片记录校验位，可通过校验信息反计算来恢复丢失的信息，即保证了高可用又提升了磁盘利用率。RAID6 在 RAID5 的基础上记录 2 块校验信息，提供更好的高可用，但性能相对会降低。

认识分部署文件系统 HDFS：

将一个大的文件分成很多片，存储在多台服务器上。可以通过横向扩展（增加服务器）来提升并发处理性能。其中 NameNode 类似文件控制块，DataNode 即数据块与单服务器文件系统类似。DataNode 通过相互复制（跨机架、保持 3 个备份）来提高其高可用性，NameNode 和 DataNode 之间通过心跳机制来监测、恢复数据、再复制等从而维持其高可用。

学习空间复杂度和时间复杂度：

算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

时间复杂度是一个函数，它定性描述该算法的运行时间。时间复杂度常用大 O 符号表述，一般不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷（n 表示）时的情况。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它也是问题规模 n 的函数。

学习数据结构相关知识：

数组：线性表的一种，一块连续的内存区，因此元素的访问时间复杂度是 O(1)，但是插入数据和删除数据操作复杂，还有越界的风险。

链表：也是线性表，但在内存中是分散的，访问时间复杂度是 O(n)，插入数据和删除数据操作简便，而且链表长度几乎没有限制（不超过内存空间的情况下）

Hash 表：哈希表是根据键（Key）而直接访问在内存储存位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，从而加速了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

栈：也是一种线性表结构，实现上可以是数组也可以是链表。它规定了数据存取的规则后进先出——被插入的数据会放到线性表头部，读取时也是从线性表的头部开始。

队列：队列的实现结构和栈一样，但是它的存取规则是先进先出——被插入的数据被放到线性表尾部，而读取的时候总是从线性表的头部开始。

树：是一种抽象数据类型，用来模拟具有树状结构性质的数据集合。它是由 n 个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

跳表：是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

递归：是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

贪心：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。对于大部分的问题，贪心法通常都不能找出最佳解，因为他们一般没有测试所有可能的解。贪心法容易过早做决定，因而没法达到最佳解。不过也有例外，在某些图论上可以得到最优解，如著名的 Prim 算法、Kruskal 算法均为贪心算法。

动态规划：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。著名的动态规划算法有：最长公共子序列、Floyd-Warshall 算法、Viterbi 算法等等。

遗传算法：最初是借鉴了进化生物学中的一些现象而发展起来的搜索算法，这些现象包括遗传、突变、自然选择以及杂交等等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。遗传算法擅长解决的问题是全局最优化问题，例如，解决时间表安排问题就是它的一个特长，很多安排时间表的软件都使用遗传算法，遗传算法还经常被用于解决实际工程问题。