硬盘简介

* 磁头（head）：主要就是读取磁盘表面磁方向和改变其方向，每个盘面有一个磁头，它极其贴近地悬浮在盘面上，但是绝对不与盘面接触，否则会损坏磁头和盘面 * 磁道（track）：磁道是单个盘面上的同心圆，当磁盘旋转时，磁头若保持在一个位置上，则每个磁头都会在磁盘表面划出一个圆形轨迹，这些圆形轨迹就叫做磁道，一个盘面上的磁道可以有成千上万个。相邻磁道之间并不是紧挨着的，这是因为磁化单元相隔太近时磁性会产生相互影响，同时也为磁头的读写带来困难。 * 柱面（cylinder）：在有多个盘片构成的盘组中，由不同盘片的面，但处于同一半径圆的多个磁道组成的一个圆柱面。 * 扇区（sector）：磁盘上的每个磁道被等分为若干个弧段，这些弧段便是硬盘的扇区（Sector）。硬盘的第一个扇区，叫做引导扇区。扇区是被间隙（gap）分割的圆的片段，间隙未被磁化成0或者1。注意，扇区是读写磁盘最基本的单位，如果一个扇区因为某种原因被破坏，那么整个扇区的数据都会受影响。

注意：硬盘的最小存储单位就是扇区了(一般为512字节)，而且硬盘本身并没有block的概念

操作系统的文件系统

文件系统不是一个扇区一个扇区的来读数据，太慢了，所以有了block（块）的概念，它是一个块一个块的读取的，block才是文件存取的最小单位。 先来知道是哪种文件系统 也可以直接查看某个分区的详情 得出块大小为4K. 每次访问磁盘的数据，需要将磁盘的数据(4k)加载到RAM中。

数据的查询

上图，有一个table，其中每行的数据大小为128字节，所以一个扇区能存四行数据，假如表大小为100行，则需要100/4=25个扇区。 那么当表很大时候，比如占用的百万个扇区，那么查询的效率是很低的，因为目前的查询是毫无顺序 的，所以我们要建立索引

索引

假设索引的id占用大小为8字节，pointer大小为8字节，一个扇区能存的index个数为512/16=32个，那么这张表的索引需要占用的扇区为100/32≈4个(超过三个)，所以，通过索引来访问，我们最多需要4个扇区就可以定位table中的那一项数据，然后再去访问数据(此操作也需要访问一个扇区来完成).所以最终访问的max扇区数量为 5。 但是，index也不断增长怎么办?,table扩增10倍，则index需要40个扇区

多级索引

建立二级索引，其中每行的point指向一级索引的一个扇区(每个扇区里有32个数据),假设二级索引的每行需要16字节 ，每一个point指向一级index的一个扇区，所以额外再需要2个扇区(40/32≈2)来存储二级索引.

这就是B-Tree和B+Tree的基本思想 把上图右旋90度，结构就是一个树

B-Tree

对于m阶B-Tree

1.根结点至少有两个子女。 2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m 3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m 4.所有的叶子结点都位于同一层。 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划

B-Tree主要用于文件系统以及部分数据库索引，如MongoDB.

B+Tree

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。 2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树的优势：

1.单一节点存储更多的元素，使得查询的IO次数更少。(每读取一块的数据中，能查询的节点更多) 2.所有查询都要查找到叶子节点，查询性能稳定。 3.所有叶子节点形成有序链表，便于范围查询。(B-Tree通过中序遍历，操作麻烦)