Week_08 总结
机械硬盘：
扇区和磁道
扇区是磁盘的最小组成单元，通常是 512 字节。（由于不断提高磁盘的大小，部分厂商设定每个扇区的大小是 4096 字节）
磁头和柱面
硬盘通常由重叠的一组盘片构成，每个盘面都被划分为数目相等的磁道，并从外缘的“0”开始编号，具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面。磁盘的柱面数与一个盘面上的磁道数是相等的。由于每个盘面都有自己的磁头，因此，盘面数等于总的磁头数。
磁盘容量计算
存储容量 ＝ 磁头数 × 磁道(柱面)数 × 每道扇区数 × 每扇区字节数
每个磁道的扇区数一样是说的老的硬盘，外圈的密度小，内圈的密度大，每圈可存储的数据量是一样的。新的硬盘数据的密度都一致，这样磁道的周长越长，扇区就越多，存储的数据量就越大。
块/簇
磁盘块/簇（虚拟出来的）。 块是操作系统中最小的逻辑存储单位。操作系统与磁盘打交道的最小单位是磁盘块。在 Windows 下如 NTFS 等文件系统中叫做簇；在 Linux 下如 Ext4 等文件系统中叫做块（block）。每个簇或者块可以包括 2、4、8、16、32、64…2 的 n 次方个扇区。
为什么存在磁盘块？
读取方便：由于扇区的数量比较小，数目众多在寻址时比较困难，所以操作系统就将相邻的扇区组合在一起，形成一个块，再对块进行整体的操作。
分离对底层的依赖：操作系统忽略对底层物理存储结构的设计。通过虚拟出来磁盘块的概念，在系统中认为块是最小的单位。
page
操作系统经常与内存和硬盘这两种存储设备进行通信，类似于“块”的概念，都需要一种虚拟的基本单位。所以，与内存操作，是虚拟一个页的概念来作为最小单位。与硬盘打交道，就是以块为最小单位。
扇区、块/簇、page 的关系
扇区： 硬盘的最小读写单元
块/簇： 是操作系统针对硬盘读写的最小单元
page： 是内存与操作系统之间操作的最小单元。
磁盘读取响应时间
读写一次磁盘信息所需的时间可分解为：寻道时间、旋转延迟时间、传输时间。为提高磁盘传输效率，软件应着重考虑减少寻道时间和延迟时间。
因此，机械硬盘对顺序读写是非常友好的，对随机读写是不友好的
固态硬盘
https://zhuanlan.zhihu.com/p/104995703?utm_source=wechat_session
结构
SSD 由控制单元和存储单元（FLASH 芯片、DRAM 芯片）组成。数据操作无机械过程，因此读写能力与机械硬盘相比是量级的提升。
SSD 中一般有多个 NAND-Flash，每个 NAND-Flash 包含多个 Block，每个 Block 包含多个 Page。由于 NAND 的特性，存取都必须以 Page 为单位，即每次读写至少是一个 Page。通常地，每个 Page 的大小为 4K 或者 8K。
特性
只能读写单个 Page，不能覆盖写某个 Page。如果要覆盖写，必须先要清空里面的内容，再写入。由于清空内容的电压较高，必须是以 Block 为单位进行清空，因此，没有空闲的 Page 时，必须要找到没有有效内容的 Block，先擦除再选择空闲的 Page 写入。
SSD 中也会维护一个 mapping table，维护逻辑地址到物理地址的映射。每次读写时，可以通过逻辑地址直接查表计算出物理地址，与传统的机械磁盘相比，省去了寻道时间和旋转时间。
ssd 写入流程
新写入
找到一个空闲 Page。
数据写入到空闲 Page。
更新 mapping table。
覆盖写
SSD 不能覆盖写，因此先找到一个空闲 pageH。
读取 Page-G 中的数据到 SSD 内部的 buffer 中，把更新的字节更新到 buffer。
buffer 中的数据写入到 H。
更新 mapping table 中 G 页，置为无效页。
更新 mapping table 中 H 页，添加映射关系。
如果在覆盖写操作比较多的情况下，会产生较多的无效页，类似于磁盘碎片，此时需要 SSD 的 GC 机制来回收这部分空间了。
B+ tree
传统数据库在进行数据存储时，使用了 B+树的方式进行磁盘数据的存储。
一个节点可以存放多个数据，查找一个节点的时候可以有多个元素，大大提升查找效率，这就是为什么数据库索引用的就是 B+树，因为索引很大，不可能都放在内存中，所以通常是以索引文件的形式放在磁盘上，所以当查找数据的时候就会有磁盘 I/O 的消耗，而 B+树正可以解决这种问题，减少与磁盘的交互，因为进行一次 I/O 操作可以得到很多数据，增大查找数据的命中率。
单个节点可以存储更多的数据，减少 I/O 的次数。
查找性能更稳定，因为都是要查找到叶子结点。
叶子结点形成了有序链表，便于查询。
数据读写时延由最终的 io 时延决定，而最终的 io 操作，又是基于块的随机操作，这限制了其性能的提升。
LSM tree
LSM 被设计来提供比传统的 B+树或者 ISAM 更好的写操作吞吐量，通过消去随机的本地更新操作来达到这个目标。
基于硬盘顺序读写友好的特性，lsm tree 利用这种特性，通过 tree 合并的方式，以连续写的方式进行数据存储，写性能优秀，但读性能不好，用于写多读少的场景。
文件管理
linux 系统是通过 inode 进行文件管理的，每个文件对应一个 inode 结构。inode 表明了这个文件的相关数据分布在哪些块上。
如何提高数据读写的能力？
Raid
通过并发写入磁盘，来提升数据的读写能力和满足数据的高可用。提升的效率取决于并发读写磁盘的数量
raid0
将一个文件进行分片，不同分片并行读写到不同磁盘中，提高了读写能力。但由于硬盘的使用寿命文件，数据高可用性会很差，一个分片丢失导致整个文件不可用。
raid1
数据同时写入两块磁盘，高可用得到一定的保证，但性能并未提升。
raid10
结合了 raid0 和 raid1，提高了数据的读写性能和满足了高可用需求。缺点是磁盘利用效率太低，一半的磁盘在存储备份数据。（至少需要 4 块磁盘，分两组，组与组之间做 raid1，组内做 raid0）
raid5
文件分片后，多个分片计算校验位，并存储校验位，当某个磁盘的数据损坏时，通过校验位和其他数据分片可以计算得到丢失的数据分片，从而保证数据的高可用
raid6
较 raid5 又新增了一个校验位，防止系统同时出现两块盘异常的情况。
分布式文件系统
既然数据的读写能力的提升取决于并发访问的磁盘的数量，而一台主机磁盘数量有限，如果需要对读写性能进一步的提升，办法是将多台主机联合起来，增加并发访问磁盘的能力。
namenode：角色和 inode 类似，记录着文件的元信息，如文件名，副本数，数据记录在什么位置(哪个 DataNode，什么位置）等
datanode：进行数据存储的节点。
当客户端进行写入时，namenode 通过计算，获取合适的 datanode，然后客户端将数据写入到相应的 datanode 上，该 datanode 会对写入的数据进行副本复制。
当节点 down 机或数据丢失时，namenode 通过与 datanode 之间的心跳检测，判断该节点失效。同时将丢失的数据块，复制到新的数据块上，保证数据的副本数。namenode 上记录着所有 datanode 上存储的数据块信息。
常见数据结构与 hash 表原理分析
NP ?= P 指在多项式时间复杂度内，能验证答案正确的前提下，能不能找出一个多项式时间复杂度内能解决问题的解
数组
内存空间连续
数据长度一致，即类型相同
通过下标访问，时间复杂度是 O(1)
链表
内存空间零散
查找复杂度 O(n)
增删比数组高效
hash 表
计算 key 得到 value 对应的位置，获取 value
栈
在链表或者数组的基础上，增加了限制条件：后进先出。
队列
在链表或者数组的基础上，增加了限制条件：先进先出。
先自己入队，然后出队，判断是否是有钱人。
不是，则所有好友入队，然后好友 BOB 出队，判断是否是有钱人。
不是则他的所有的好友入队，然后出队下一个好友继续进行上述操作，直到找到。
过程同上，这是一种广度优先遍历，如果要获取路径，则记录其反向路径，最终得到完整路径
二叉搜索树
左子树上所有结点的值均小于或等于它的根结点的值。
右子树上所有结点的值均大于或等于它的根结点的值。
左、右子树也分别为二叉排序树。
平衡二叉树
从任何一个节点出发，左右子树深度之差的绝对值不超过 1。
左右子树仍然为平衡二叉树。
平衡的维护
维护方法
节点维护其自身高度 H = 1 + max(左 H, 右 H)
检查是否平衡: | 左 H - 右 H | > 1
旋转
左旋：左 H - 右 H < -1 && x.左 H- x.右 H <= 0
y.right= x. left
x.left = y
更新 x 和 y 的高度 H
右旋：左 H - 右 H > 1 && x.左 H- x.右 H >= 0
y.left = x.right
x.right = y
更新 x 和 y 的高度 H
右左旋：左 H - 右 H < -1 && x.左 H- x.右 H > 0
Y 的右子树进行右旋
x.left = z.right
z.right = x
y.right = z
更新 x，z 高度
对 Y 进行左旋
左右旋：左 H - 右 H > 1 && x.左 H- x.右 H < 0
Y 的左子树进行左旋
x. right = z.left
z.left = x
y.left = z
更新 x，z 高度
对 Y 进行右旋
维护时机
插入后从叶子到根进行平衡性检查，然后进行旋转
删除后从叶子到根进行平衡性检查，然后进行旋转
还未添加个人签名 2018.09.18 加入
还未添加个人简介
评论