第八周作业及总结

请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。

硬盘工作原理：机械硬盘通过磁头移动和磁盘旋转进行磁盘数据访问，磁头位移相比磁盘旋转速度要慢的多，数据离散分布下，查询相对耗时，固态硬盘相比机械硬盘要快的多。若需要提升磁盘的读写性能，可通过磁盘阵列，写入数据时同时写入多个磁盘，阵列主要有 RAID0,RAID1,RAID10,RAID5,RAID6,读写性能依次降低，可靠性依次提高，RAID5,RAID6 利用多个磁盘分散保存若干个校验值，用于磁盘宕机下的数据恢复。

常见数据结构的读写特性及复杂度：

线性表：

数组，存储连续，数据类型相同，通过下标查询的时间复杂度为 O（1）,排序的数组通过二分查询元素的时间复杂度为 O(logN),当需要删除或添加元素，需要进行位移。

链表是通过指针遍历，删除及添加元素相对方便。

队列是先进先出，堆栈是后进先出，都可以通过数组或链表实现。

跳表通过在链表上添加多级索引的链表，可以快速查询，hash 表通过 hash 函数计算键值对的位置，时间复杂度为 0（1），在 hash 冲突时，变成链表会降低查询效率。

二叉排序树需要平衡才能保证查询效率，添加节点时需要经过二次旋转进行平衡，删除节点时需要多次旋转平衡。

红黑树相对二叉树平衡性降低，在需要多次删除添加节点，平衡次数更少。特征：根节点是黑节点，叶子节点是黑色的空节点，从根节点到叶子节点不存在两个连续的红节点，到叶子节点存在相同数量的黑节点。

常见的算法：穷举算法，递归算法，贪心算法，改进的贪心算法，动态规范算法，遗传算法。

http 建立连接的三次握手，断开连接的四次挥手，NIO 利用多路复用完成大量连接的处理工作。主要通过系统 select,epoll 调用进行事件监听。