Ⅰ 程序员必备知识（操作系统5-文件系统）
本篇与之前的第三篇的内存管理知识点有相似的地方
对于运行的进程来说，内存就像一个纸箱子, 仅仅是一个暂存数据的地方， 而且空间有限。如果我们想要进程结束之后，数据依然能够保存下来，就不能只保存在内存里，而是应该保存在 外部存储 中。就像图书馆这种地方，不仅空间大,而且能够永久保存。
我们最常用的外部存储就是 硬盘 ，数据是以文件的形式保存在硬盘上的。为了管理这些文件，我们在规划文件系统的时候，需要考虑到以下几点。
第一点,文件系统要有严格的组织形式，使得文件能够 以块为单位进行存储 。这就像图书馆里，我们会给设置一排排书架，然后再把书架分成一个个小格子，有的项目存放的资料非常多，一个格子放不下，就需要多个格子来进行存放。我们把这个区域称为存放原始资料的 仓库区 。
第二点,文件系统中也要有 索引区 ，用来方便查找一个文件分成的多个块都存放在了什么位置。这就好比，图书馆的书太多了,为了方便查找,我们需要专门设置一排书架,这里面会写清楚整个档案库有哪些资料,资料在哪个架子的哪个格子上。这样找资料的时候就不用跑遍整个档案库,在这个书架上找到后，直奔目标书架就可以了。
第三点,如果文件系统中有的文件是热点文件,近期经常被读取和写入，文件系统应该有 缓存层 。这就相当于图书馆里面的热门图书区,这里面的书都是畅销书或者是常常被借还的图书。因为借还的次数比较多,那就没必要每次有人还了之后，还放回遥远的货架，我们可以专门开辟一个区域, 放置这些借还频次高的图书。这样借还的效率就会提高。
第四点,文件应该用 文件夹 的形式组织起来，方便管理和查询。这就像在图书馆里面，你可以给这些资料分门别类,比如分成计算机类.文学类.历史类等等。这样你也容易管理，项目组借阅的时候只要在某个类别中去找就可以了。
在文件系统中，每个文件都有一个名字,这样我们访问一个文件，希望通过它的名字就可以找到。文件名就是一个普通的文本。 当然文件名会经常冲突,不同用户取相同的名字的情况还是会经常出现的。
要想把很多的文件有序地组织起来,我们就需要把它们成为 目录 或者文件夹。这样,一个文件夹里可以包含文件夹,也可以包含文件,这样就形成了一种 树形结构 。而我们可以将不同的用户放在不同的用户目录下，就可以一定程度上避免了命名的冲突问题。
第五点，Linux 内核要在自己的内存里面维护一套数据结构，来保存哪些文件被哪些进程打开和使用 。这就好比，图书馆里会有个图书管理系统，记录哪些书被借阅了，被谁借阅了，借阅了多久,什么时候归还。
文件系统是操作系统中负责管理持久数据的子系统，说简单点,就是负责把用户的文件存到磁盘硬件中,因为即使计算机断电了，磁盘里的数据并不会丢失,所以可以持久化的保存文件。
文件系统的基本数据单位是 文件 ，它的目的是对磁盘上的文件进行组织管理，那组织的方式不同,就会形成不同的文件系统。
Linux最经典的一句话是:“一切皆文件”,不仅普通的文件和目录，就连块设备、管道、socket 等，也都是统一交给文件系统管理的。
Linux文件系统会为每个文件分配两个数据结构: 索引节点(index node) 和 目录项(directory entry) ，它们主要用来记录文件的元信息和目录层次结构。
●索引节点，也就是inode, 用来记录文件的元信息，比如inode编号、文件大小访问权限、创建时间、修改时间、 数据在磁盘的位置 等等。 索引节点是文件的唯一标识 ,它们之间一一对应, 也同样都会被 存储在硬盘 中,所以索引节点同样占用磁盘空间。
●目录项，也就是dentry, 用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。多个目录项关联起来，就会形成 目录结构 ，但它与索引节点不同的是,目录项是由内核维护的一个数据结构,不存放于磁盘，而是 缓存在内存 。
由于索引节点唯一标识一个文件，而目录项记录着文件的名，所以目录项和索引节点的关系是多对一,也就是说，一个文件可以有多个别字。比如，硬链接的实现就是多个目录项中的索引节点指向同一个文件。
注意，目录也是文件，也是用索引节点唯一标识，和普通文件不同的是，普通文件在磁盘里面保存的是文件数据，而目录文件在磁盘里面保存子目录或文件。
（PS：目录项和目录不是一个东西！你也不是一个东西（^_=）， 虽然名字很相近，但目录是个文件。持久化存储在磁盘,而目录项是内核一个数据结构,缓存在内存。
如果查询目录频繁从磁盘读，效率会很低，所以内核会把已经读过的目录用目录项这个数据结构缓存在内存，下次再次读到相同的目录时，只需从内存读就可以,大大提高了 文件系统的效率。
目录项这个数据结构不只是表示目录，也是可以表示文件的。）
磁盘读写的最小单位是 扇区 ，扇区的大小只有512B大小，很明显，如果每次读写都以这么小为单位，那这读写的效率会非常低。
所以，文件系统把多个扇区组成了一个 逻辑块 ，每次读写的最小单位就是逻辑块(数据块) , Linux中的逻辑块大小为4KB,也就是一次性读写 8个扇区,这将大大提高了磁盘的读写的效率。
以上就是索引节点、目录项以及文件数据的关系，下面这个图就很好的展示了它们之间的关系:
索引节点是存储在硬盘上的数据，那么为了加速文件的访问，通常会把索引节点加载到内存中。
另外，磁盘进行格式化的时候，会被分成三个存储区域，分别是超级块、索引节点区和数据块区。
●超级块,用来存储文件系统的详细信息，比如块个数、块大小、空闲块等等。
●索引节点区,用来存储索引节点;
●数据块区，用来存储文件或目录数据;
我们不可能把超级块和索引节点区全部加载到内存,这样内存肯定撑不住，所以只有当需要使用的时候，才将其加载进内存，它们加载进内存的时机是不同的.
●超级块:当文件系统挂载时进入内存;
●索引节点区:当文件被访问时进入内存;
文件系统的种类众多，而操作系统希望 对用户提供一个统一的接口 ，于是在用户层与文件系统层引入了中间层，这个中间层就称为 虚拟文件系统(Virtual File System, VFS) 。
VFS定义了一组所有文件系统都支持的数据结构和标准接口,这样程序员不需要了解文件系统的工作原理，只需要了解VFS提供的统一接口即可。
在Linux文件系统中，用户空间、系统调用、虚拟机文件系统、缓存、文件系统以及存储之间的关系如下图:
Linux支持的文件系统也不少，根据存储位置的不同，可以把文件系统分为三类:
●磁盘的文件系统，它是直接把数据存储在磁盘中,比如Ext 2/3/4. XFS 等都是这类文件系统。
●内存的文件系统，这类文件系统的数据不是存储在硬盘的,而是占用内存空间，我们经常用到的/proc 和/sys文件系统都属于这一类,读写这类文件,实际上是读写内核中相关的数据。
●网络的文件系统,用来访问其他计算机主机数据的文件系统，比如NFS. SMB等等。
文件系统首先要先挂载到某个目录才可以正常使用，比如Linux系统在启动时,会把文件系统挂载到根目录。
在操作系统的辅助之下，磁盘中的数据在计算机中都会呈现为易读的形式，并且我们不需要关心数据到底是如何存放在磁盘中,存放在磁盘的哪个地方等等问题，这些全部都是由操作系统完成的。
那么，文件数据在磁盘中究竟是怎么样的呢?我们来一探究竟!
磁盘中的存储单元会被划分为一个个的“ 块 ”，也被称为 扇区 ,扇区的大小一般都为512byte.这说明即使一块数据不足512byte,那么它也要占用512byte的磁盘空间。
而几乎所有的文件系统都会把文件分割成固定大小的块来存储，通常一个块的大小为4K。如果磁盘中的扇区为512byte,而文件系统的块大小为4K,那么文件系统的存储单元就为8个扇区。这也是前面提到的一个问题，文件大小和占用空间之间有什么区别?文件大小是文件实际的大小，而占用空间则是因为即使它的实际大小没有达到那么大,但是这部分空间实际也被占用，其他文件数据无法使用这部分的空间。所以我们 写入1byte的数据到文本中,但是它占用的空间也会是4K。
这里要注意在Windows下的NTFS文件系统中，如果一开始文件数据小于 1K,那么则不会分配磁盘块来存储，而是存在一个文件表中。但是一旦文件数据大于1K,那么不管以后文件的大小，都会分配以4K为单位的磁盘空间来存储。
与内存管理一样,为了方便对磁盘的管理,文件的逻辑地址也被分为一个个的文件块。于是文件的逻辑地址就是(逻辑块号，块内地址)。用户通过逻辑地址来操作文件,操作系统负责完成逻辑地址与物理地址的映射。
不同的文件系统为文件分配磁盘空间会有不同的方式，这些方式各自都有优缺点。
连续分配要求每个文件在磁盘上有一组连续的块，该分配方式较为简单。
通过上图可以看到，文件的逻辑块号的顺序是与物理块号相同的,这样就可以实现随机存取了，只要知道了第一个逻辑块的物理地址, 那么就可以快速访问到其他逻辑块的物理地址。那么操作系统如何完成逻辑块与物理块之间的映射呢?实际上,文件都是存放在目录下的，而目录是一种有结构文件, 所以在文件目录的记录中会存放目录下所有文件的信息，每一个文件或者目录都是一个记录。 而这些信息就包括文件的起始块号和占有块号的数量。
那么操作系统如何完成逻辑块与物理块之间的映射呢? (逻辑块号, 块内地址) -> (物理块号, 块内地址)，只需要知道逻辑块号对应的物理块号即可,块内地址不变。
用户访问一个文件的内容,操作系统通过文件的标识符找到目录项FCB, 物理块号=起始块号+逻辑块号。 当然，还需要检查逻辑块号是否合法,是否超过长度等。因为可以根据逻辑块号直接算出物理块号，所以连续分配支持 顺序访问和随机访问 。
因为读/写文件是需要移动磁头的，如果访问两个相隔很远的磁盘块,移动磁头的时间就会变长。使用连续分配来作为文件的分配方式，会使文件的磁盘块相邻，所以文件的读/写速度最快。
连续空间存放的方式虽然读写效率高，但是有 磁盘空间碎片 和 文件长度不易扩展 的缺陷。
如下图，如果文件B被删除，磁盘上就留下一块空缺，这时，如果新来的文件小于其中的一个空缺，我们就可以将其放在相应空缺里。但如果该文件的大小大于所
有的空缺，但却小于空缺大小之和，则虽然磁盘上有足够的空缺，但该文件还是不能存放。当然了，我们可以通过将现有文件进行挪动来腾出空间以容纳新的文件,但是这个在磁盘挪动文件是非常耗时，所以这种方式不太现实。
另外一个缺陷是文件长度扩展不方便，例如上图中的文件A要想扩大一下，需要更多的磁盘空间,唯一的办法就只能是挪动的方式，前面也说了，这种方式效率是非常低的。
那么有没有更好的方式来解决上面的问题呢?答案当然有，既然连续空间存放的方式不太行，那么我们就改变存放的方式，使用非连续空间存放方式来解决这些缺陷。
非连续空间存放方式分为 链表方式 和 索引方式 。
链式分配采取离散分配的方式，可以为文件分配离散的磁盘块。它有两种分配方式:显示链接和隐式链接。
隐式链接是只目录项中只会记录文件所占磁盘块中的第一块的地址和最后一块磁盘块的地址, 然后通过在每一个磁盘块中存放一个指向下一 磁盘块的指针， 从而可以根据指针找到下一块磁盘块。如果需要分配新的磁盘块,则使用最后一块磁盘块中的指针指向新的磁盘块,然后修改新的磁盘块为最后的磁盘块。
我们来思考一个问题, 采用隐式链接如何将实现逻辑块号转换为物理块号呢?
用户给出需要访问的逻辑块号i,操作系统需要找到所需访问文件的目录项FCB.从目录项中可以知道文件的起始块号，然后将逻辑块号0的数据读入内存,由此知道1号逻辑块的物理块号，然后再读入1号逻辑块的数据进内存，此次类推，最终可以找到用户所需访问的逻辑块号i。访问逻辑块号i,总共需要i+ 1次磁盘1/0操作。
得出结论: 隐式链接分配只能顺序访问，不支持随机访问，查找效率低 。
我们来思考另外一个问题，采用隐式链接是否方便文件拓展?
我们知道目录项中存有结束块号的物理地址，所以我们如果要拓展文件，只需要将新分配的磁盘块挂载到结束块号的后面即可，修改结束块号的指针指向新分配的磁盘块，然后修改目录项。
得出结论: 隐式链接分配很方便文件拓展。所有空闲磁盘块都可以被利用到，无碎片问题，存储利用率高。
显示链接是把用于链接各个物理块的指针显式地存放在一张表中，该表称为文件分配表(FAT, File Allocation Table)。
由于查找记录的过程是在内存中进行的,因而不仅显着地 提高了检索速度 ，而且 大大减少了访问磁盘的次数 。但也正是整个表都存放在内存中的关系，它的主要的缺点是 不适 用于大磁盘 。
比如，对于200GB的磁盘和1KB大小的块，这张表需要有2亿项，每一项对应于这2亿个磁盘块中的一个块,每项如果需要4个字节，那这张表要占用800MB内存,很显然FAT方案对于大磁盘而言不太合适。
一直都在，加油！（*゜Д゜）σ凸←自爆按钮
链表的方式解决了连续分配的磁盘碎片和文件动态打展的问题，但是不能有效支持直接访问(FAT除外) ,索引的方式可以解决这个问题。
索引的实现是为每个文件创建一个 索引数据块 ，里面存放的 是指向文件数据块的指针列表 ,说白了就像书的目录一样,要找哪个章节的内容,看目录查就可以。
另外， 文件头需要包含指向索引数据块的指针 ,这样就可以通过文件头知道索引数据块的位置，再通过索弓|数据块里的索引信息找到对应的数据块。
创建文件时，索引块的所有指针都设为空。当首次写入第i块时，先从空闲空间中取得一个块， 再将其地址写到索引块的第i个条目。
索引的方式优点在于:
●文件的创建、增大、缩小很方便;
●不会有碎片的问题;
●支持顺序读写和随机读写;
由于索引数据也是存放在磁盘块的，如果文件很小，明明只需一块就可以存放的下，但还是需要额外分配一块来存放索引数据，所以缺陷之一就是存储索引带来的开销。
如果文件很大，大到一个索引数据块放不下索引信息，这时又要如何处理大文件的存放呢?我们可以通过组合的方式，来处理大文件的存储。
先来看看 链表+索引 的组合，这种组合称为 链式索引块 ，它的实现方式是在 索引数据块留出一个存放下一个索引数据块的指针 ，于是当一个索引数据块的索引信息用完了，就可以通过指针的方式，找到下一个索引数据块的信息。那这种方式也会出现前面提到的链表方式的问题，万一某个指针损坏了，后面的数据也就会无法读取了。
还有另外一种组合方式是 索引+索引 的方式，这种组合称为多级索引块，实现方式是通过一个索引块来存放多个索引数据块,一层套一层索引， 像极了俄罗斯套娃是吧๑乛◡乛๑
前面说到的文件的存储是针对已经被占用的数据块组织和管理，接下来的问题是，如果我要保存一个数据块, 我应该放在硬盘上的哪个位置呢?难道需要将所有的块扫描一遍，找个空的地方随便放吗?
那这种方式效率就太低了，所以针对磁盘的空闲空间也是要引入管理的机制，接下来介绍几种常见的方法:
●空闲表法
●空闲链表法
●位图法
空闲表法
空闲表法就是为所有空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数，注意，这个方式是连续分配的。如下图:
当请求分配磁盘空间时，系统依次扫描空闲表里的内容，直到找到一个合适的空闲区域为止。当用户撤销一个文件时，系统回收文件空间。这时，也需顺序扫描空闲表,寻找一个空闲表条目并将释放空间的第一个物理块号及它占用的块数填到这个条目中。
这种方法仅当有少量的空闲区时才有较好的效果。因为，如果存储空间中有着大量的小的空闲区,则空闲表变得很大,这样查询效率会很低。另外，这种分配技术适用于建立连续文件。
空闲链表法
我们也可以使用链表的方式来管理空闲空间，每一个空闲块里有一个指针指向下一个空闲块，这样也能很方便的找到空闲块并管理起来。如下图：
当创建文件需要一块或几块时，就从链头上依次取下一块或几块。反之，当回收空间时，把这些空闲块依次接到链头上。
这种技术只要在主存中保存一个指针, 令它指向第一个空闲块。其特点是简单,但不能随机访问，工作效率低，因为每当在链上增加或移动空闲块时需要做很多1/0操作,同时数据块的指针消耗了一定的存储空间。
空闲表法和空闲链表法都不适合用于大型文件系统，因为这会使空闲表或空闲链表太大。
位图法
位图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。
当值为0时，表示对应的盘块空闲，值为1时，表示对应的盘块已分配。它形式如下:
在Linux文件系统就采用了位图的方式来管理空闲空间,不仅用于数据空闲块的管理,还用于inode空闲块的管理，因为inode也是存储在磁盘的，自然也要有对其管理。
前面提到Linux是用位图的方式管理空闲空间，用户在创建一个新文件时， Linux 内核会通过inode的位图找到空闲可用的inode,并进行分配。要存储数据时，会通过块的位图找到空闲的块，并分配，但仔细计算一下还是有问题的。
数据块的位图是放在磁盘块里的，假设是放在一个块里,一个块4K,每位表示一个数据块,共可以表示4 * 1024 * 8 = 2^15个空闲块,由于1个数据块是4K大小，那么最大可以表示的空间为2^15 * 4 * 1024 = 2^27个byte,也就是128M。
也就是说按照上面的结构，如果采用（一个块的位图+ 一系列的块），外加一（个块的inode的位图+一系列的inode）的结构能表示的最大空间也就128M,
这太少了，现在很多文件都比这个大。
在Linux文件系统，把这个结构称为一个 块组 ，那么有N多的块组,就能够表示N大的文件。
最终,整个文件系统格式就是下面这个样子。
最前面的第一个块是引导块,在系统启动时用于启用引导，接着后面就是一个一个连续的块组了,块组的内容如下:
● 超级块 ,包含的是文件系统的重要信息，比如inode总个数、块总个数、每个块组的inode个数、每个块组的块个数等等。
● 块组描述符 ,包含文件系统中各个块组的状态,比如块组中空闲块和inode的数目等，每个块组都包含了文件系统中“所有块组的组描述符信息”。
● 数据位图和inode位图 ，用于表示对应的数据块或inode是空闲的，还是被使用中。
● inode 列表 ，包含了块组中所有的inode, inode 用于保存文件系统中与各个文件和目录相关的所有元数据。
● 数据块 ，包含文件的有用数据。
你可以会发现每个块组里有很多重复的信息，比如 超级块和块组描述符表，这两个都是全局信息，而且非常的重要 ，这么做是有两个原因:
●如果系统崩溃破坏了超级块或块组描述符,有关文件系统结构和内容的所有信息都会丢失。如果有冗余的副本,该信息是可能恢复的。
●通过使文件和管理数据尽可能接近，减少了磁头寻道和旋转,这可以提高文件系统的性能。
不过，Ext2 的后续版本采用了稀疏技术。该做法是，超级块和块组描述符表不再存储到文件系统的每个块组中,而是只写入到块组0、块组1和其他ID可以表示为3、5、7的幂的块组中。
在前面，我们知道了一个普通文件是如何存储的，但还有一个特殊的文件,经常用到的目录，它是如何保存的呢?
基于Linux 一切切皆文件的设计思想，目录其实也是个文件,你甚至可以通过vim打开它，它也有inode, inode 里面也是指向一些块。
和普通文件不同的是， 普通文件的块里面保存的是文件数据，而目录文件的块里面保存的是目录里面一项一项的文件信息 。
在目录文件的块中，最简单的保存格式就是 列表 ，就是一项一项地将目录下的文件信息(如文件名、文件inode.文件类型等)列在表里。
列表中每一项就代表该目录下的文件的文件名和对应的inode,通过这个inode,就可以找到真正的文件。
通常，第一项是“则”，表示当前目录,第二项是.，表示上一级目录, 接下来就是一项一项的文件名和inode。
如果一个目录有超级多的文件,我们要想在这个目录下找文件,按照列表一项一项的找,效率就不高了。
于是，保存目录的格式改成 哈希表 ，对文件名进行哈希计算,把哈希值保存起来,如果我们要查找一个目录下面的文件名，可以通过名称取哈希。如果哈希能够匹配上,就说明这个文件的信息在相应的块里面。
Linux系统的ext文件系统就是采用了哈希表，来保存目录的内容,这种方法的优点是查找非常迅速，插入和删除也较简单,不过需要一些预备措施来避免哈希冲突。
目录查询是通过在磁盘上反复搜索完成，需要不断地进行/0操作,开销较大。所以,为了减少/0操作,把当前使用的文件目录缓存在内存，以后要使用该文件时只要在内存中操作，从而降低了磁盘操作次数,提高了文件系统的访问速度。
感谢您的阅读，希望您能摄取到知识！加油！冲冲冲！（发现光，追随光，成为光，散发光！）我是程序员耶耶！有缘再见。<－biubiu－⊂(`ω´∩)
Ⅱ ClickHouse存储结构及索引详解
本文基于ClickHouse 20.8.5.45版本编写，操作系统使用的是CentOS 7.5，主要介绍MergeTree表引擎的存储结构以及索引过程。
刚刚创建的表只在数据目录下生成了一个名为 test_merge_tree 文件夹(具体路径为data/default/test_merge_tree)，并没有任何数据，接下来往该表里面插入一条数据，看看会生成哪些文件。
在test_merge_tree目录下使用tree命令可以看到刚刚的那条命令生成了一个名为 200002_1_1_0 的文件夹。
在介绍这些文件之前先介绍一下200002_1_1_0这个目录的命名规则
当分区发生合并时，新的分区目录名称命名规则将会在接下来介绍，这里不做详述。
在介绍这部分之前，需要先将min_compress_block_size配置改小，以方便分析mrk2和bin文件，其默认值为65535。
修改方法为在 users.xml 文件的 profiles 里面增加以下配置
修改完后重启clickhouse-server服务，然后再用以下命令查看是否修改成功
刚刚已经插入了一条数据，但是那一条数据不具有代表性，所以这次决定多插入几条数据再来分析。
上面这条命令产生了个新的分区目录 200002_2_2_0 ，此目录下的文件前面已经讲过，现在重点分析以下几个文件的存储格式
MergeTree表会按照主键字段生成primary.idx，用于加快表查询。前面创建表时使用的是(Id, Name)两个字段作为主键，所以每隔index_granularity行数据就会取(Id, Name)的值作为索引值，由于index_granularity被设置为2，所以每隔两行数据就会生成一个索引。也就是说会使用(3,'Lisa'), (6,'Meimei'), (31,'vincent')作为索引值。
这里我只介绍第一个索引(3,'Lisa')的存储格式，剩下的可以自己去梳理。Id是UInt64类型的，所以使用8字节来存储。从上图可以看出前8个字节为0x03，以小端模式来存储，接下来我们可以看到其它文件都是以小端模式来存储。Name是String类型，属于变长字段，所以会先使用1个字节来描述String的长度，由于Lisa的长度是4，所以第9个字节为0x04，再接下来就是Lisa的ASCII码。
mrk2文件格式比较固定，primary.idx文件中的每个索引在此文件中都有一个对应的Mark，Mark的格式如下图所示：
通过primary.idx中的索引寻找mrk2文件中对应的Mark非常简单，如果要寻找第n(从0开始)个index，则对应的Mark在mrk2文件中的偏移为n*24，从这个偏移处开始读取24 Bytes即可得到相应的Mark。
bin文件由若干个Block组成，由上图可知Id.bin文件中包含两个Block。每个Block主要由头部的Checksum以及若干个Granule组成，Block的格式如下图所示：
每个Block都会包含若干个Granule，具体有多少个Granule是由参数min_compress_block_size控制，每次Block中写完一个Granule的数据时，它会检查当前Block Size是否大于等于min_compress_block_size，如果满足则会把当前Block进行压缩然后写到磁盘中，不满足会继续等待下一个Granule。结合上面的INSERT语句，当插入第一个Granule(3, 4)时，数据的的size为16，由于16 < 24所以会等第二个Granule，当插入第二个Granule(6, 12)后数据的size为32，由于32 > 24所以会把(3, 4, 6, 12)压缩放到第一个Block里面。最后面的那个31由于是最后一条数据，就放到第二个Block里面。
partition.dat文件里面存放的是分区表达式的值，该分区表达式生成的值为200002，UInt32类型，转换成16进制就是0x00030d42。
minmax文件里面存放的是该分区里分区字段的最小最大值。分区字段Birthday的类型为Date，其底层由UInt16实现，存的是从1970年1月1号到现在所经过的天数。通过上面的INSERT语句我们可以知道Birthday的最小值为2000-02-03，最大值为2000-02-08。这两个时间转换成天数分别为10990和10995，再转换成16进制就是0x2aee和0x2af3。
属于同一个分区的不同目录，ClickHouse会在分区目录创建后的一段时间自动进行合并，合并之后会生成一个全新的目录，以前老的分区目录不会立马删除，而是在合并后过一段时间再删除。新的分区目录名称遵循以下规则：
所以上面的两个分区目录200002_1_1_0和200002_2_2_0在过一段时间后最终会变成一个新的分区目录200002_1_2_1。由此可见如果你频繁插入数据会产生很多分区目录，在合并的时候会占用很多资源。所以最好一次插入很多条数据，尽量降低插入的频率。
通过上面的介绍相信大家已经对ClickHouse的索引结构有所了解，接下来用一张图简要描述Id字段的索引过程。
其它列的索引过程类似，这里就不一一赘述了，有兴趣的朋友可以自己去研究。
本文通过一个简单的例子来分析ClickHouse的存储结构，整个逻辑力求简洁明了，希望通过本文能够让喜欢ClickHouse的朋友对它的索引有个清晰的认识。
Ⅲ 【操作系统问题】文件系统采用多重索引结构搜索文件内容
1）该文件需要占用多少个页面
根据题目中给定的信息，该文件的逻辑大小为64MB，每个物理块的块长为2k字节。因此，该文件需要占用64MB/2k=32k个页面。
（2）如果使用二重索引结构来存储该文件，是否能够满足该文件的所需要的物理空间需求，为什么？
在二重索引结构中，每个索引页面都包含若干个块号，每个块号占8个字节。如果假定每个索引页面能够存储64个块号，则一个索引页面的大小为64*8=512字节。
在这种情况下，该文件的实际物理空间需求为32k*2k=64MB，而每个索引页面的大小为512字节，因此，一个索引页面无法满足该文件所需要的物理空间需求，即使使用二重索引结构来存储该文件，也无法满足需求。
三重索引结构中，每个页面都包含若干个索引页面的块号，每个块号占8个字节。如果假定每个页面能够存储64个块号，则一个页面的大小为64*8=512字节。
在这种情况下，该文件的实际物理空间需求为32k2k=64MB，而每个页面的大小为512字节，因此，使用三重索引结构来存储该文件时，该文件实际所占的物理空间为64MB/512=128k个页面。也就是说，该文件实际占用的物理空间为128k512=64MB字节。
需要注意的是，上面的计算只考虑了索引页面的大小，并没有考虑逻辑块号在物理块中所占的空间。因此，如果要准确地计算该文件实际所占的物理空间，还扒汪银需要考虑逻辑块号在物理块中所占的空间。
具体来说，如果逻辑块号在物理块中春宴占据了陵启一定的空间，那么该文件实际所占的物理空间可能会比上面计算出来的64MB要大一些。但是，由于没有具体的信息来描述逻辑块号在物理块中所占的空间，因此无法进一步计算。
Ⅳ 操作系统-文件系统
人们对信息有存储的需求，早期计算机信息在保存在纸带上，存和读都不方便，且容量很低，而存储信息的需求未能得到满足，到了磁盘存储器的出现，对程序和数据等信息的管理的发展才得到质的飞跃。出现桐返瞎文件系统是需要把信息以一种单元，即文件的形式，存储在磁盘或其它外部存储介质上，导致了文件系统的出现。
文件系统是操作系统中统一管理信息资源的一种软件。它管理文件的存储、检索、更新、提供安全可靠的共享和保护手段，并且方便用户使用。从用户的角度看，文件系统负责为用户建立文件、读写文件、修改文件、复制文件和撤销文件等，还能对文件按名存取。
文件是一组带标识的、在逻辑上有完整意义的信息项的序列，这里的标识就是文件名，”信息项“构成了文件的内容。
外存是相对内存而言，主要用来存储信息，其特点是断电后仍可保存信息，容量大，速度较慢，成本较低等
外存储设备通常由驱动部分和存储介质两部分组成，存储介质又常被卷。
存储介质有：磁带、磁盘、光盘、闪存
其中磁带是顺序存储，只能读了前面磁带的内容才能读后面，存取都一样，不能跳着读取，因此磁带适合存储不经常变化的内容，比如放歌。
磁盘支持随机读取，磁盘由带有读写磁头的机械臂和磁盘组成，磁盘像光盘，上面有磁性材料。系统对磁盘初始化时，会划分出一些同心圆，称为磁道，信息只能存储在磁道上，磁道分世源会被分成多个弧段，称为扇区，每个磁道有4-32个扇区。使用时，驱动器的马达带去磁盘高速匀局空速旋转，磁头一直停留在盘面表面上方并可以在不同磁道移动，当找到目标磁道时，碰头不动，磁盘依然转动，这时经过磁头的信息就被读出来可写进去。
光盘是激光作用下材料变化的非磁记录介质。
闪存是电荷擦除，支持随机存取，没有机械运动部件，寿命和可靠性高。
文件可以从不同的维度来进行分类：
按用途的方式分类：
按文件组织形式分类：
文件逻辑结构就是用户所看到的文件组织形式，文件逻辑结构是经过抽象的结构，所描述的是文件中信息组织形式。按逻辑结构可以把文件划分成三类：无结构的字符流式文件（由字节组成）、定长记录文件和不定长记录文件（由记录组成）；
文件的物理结构是指文件存储在外储设备上的结构，有三种存储结构：顺序存储、链式存储、索引存储；
顺序存储：文件存在连续的空间上，只要知道到起始地址和长度就可以读取文件。
优点：支持随机存取、
缺点：不支持动态扩充，容易产生碎片。
链式存储：文件存在不连续的物理块中，文件控制块保存第一个物理块的指针，之后每个物理块都有一个指针指向下一个物理块地址，如FAT文件系统
优点：可以动态扩充，提高磁盘利用空间；修改添加快。
缺点：
1.可靠性低。若其中某个物理块出错会导致后面全部块读取不到。
2.存取速度慢，不适于随机存取文件，需要从首个物理块一直读取到物理块；
索引存储：使用一张表来存储索引，每个索引指向逻辑文件的信息块。
优点：可以动态扩充，支持随机存取；
缺点：较多的寻道次数和寻道时间；索引表本身增加了存储空间的开销。
文件目录主要是用途是为了管理和索引文件，其结构简单说是一张表，表中存储着文件名、文件控制块、物理地址，通过文件名可以快速的读取到对应的文件。
一级目录是一张线性表，优点是：结构简单、实现简单；缺点：无法解决不同用户的文件名相同；文件多时查找慢。
二级目录是分为主目录和用户目录，主目录给出所有用户目录所在物理位置； 而用户目录则给出所有文件的FCB;优点：不同用户文件可以重名、查找速度比一级目录快、能实现文件共享
多级目录（树形目录）除了最低一级物理块装有文件信息外，其它每一级的目录存储的都是下一级的目录或文件说明信息，多级目录存在唯一的概目录。优点是层次清楚、解决文件重名问题、查找速度快。
目录是指文件路径。
目录项是是文件控制块以一条记录的形式存储在目录文件中。
目录文件是多个文件控制块集中在一起形成的文件。
参考：《操作系统》机械工业出版社 2017年版
Ⅳ 操作系统关于文件索引的题目求解！！！急！！！！
因为一个目录文件最多可以由4个磁盘块组成，读目录和下级目录野绝的时候，在最好的情况下，总能在第一个磁盘块上就能找到所需的下级目录信息，所以ADKQ四个目录读四次就可以了，此后是读文差滑件，理想情况下所需页面可以通过前10个索引直接找到，此时只需再读一次就能读到所需页了，结果最少共用5次
最坏情况下，每个目录都存放在4个磁盘块的最后一个上，因此每个目录都得读四次，一共4*4=16次，而找到文件后，所需页面又得通过2级索引去找，这样一来2级索引颂庆姿表读一次，1级索引表又读一次，页面本身内容再读一次，又需2+1=3次，所以最坏情况就是16+3=19次
有问题欢迎追问！
Ⅵ 操作系统，关于文件的问题如题： 已知块大小为4K，块号占4B，问采用几级索引方式存储
首先我认贺孙猛为题目条件有问题，没有告知文件大小就问索引数量。如果直接做的话，通常我们用一个盘块来作为一个索引块的大小，看一个索引块中能放几个盘块号，所以第一步得出有1K个盘块，每个盘块大小为4K，所以如果每个盘块号对应一禅桥个盘块，一共能存储4M的文件，如果文件超出4M，就采用2级索引，既可存储的盘块数量变成1K*1K，所以可允许的最大长度凯颤就是4G，不知道说清楚了没有。
Ⅶ 操作系统-04-操作系统的存储管理和设备管理
早期的计算机由于结构较为简单，存储容量小，并不需要过多的的存储管理。
随着计算机和程序越来越复杂，使得存储管理成为必要。
单一连续分配是最简单的内存分配方式
只能在单用户、单进程的操作系统中使用
固定分区分配是支持多道程序的最简单存储分配方式
内存空间被划分为若干固定大小的区域
每个分区只提供给一个程序使用，互不干扰
根据进程实际需要，动态分配内存空间
不需要新建空闲链表节点
只需要把空闲区的容量增大为包括回收区的容量即可
将回收区和空闲区合并
新的空闲区使用原来回收区的地址
将两个空闲区和中间的回收区合并
新的空闲区使用空闲区1的地址
为回收区创建新的空闲节点
将该节点插入到相应的空闲区链表中
上面的部分主要是从物理的角度讲解内存管理，这部分主要是讲解操作系统是怎么管理进程的内存空间。
字块 是相对于物理设备的定义， 页面 是相对逻辑空间的定义。
页式存储管理主要是将进程逻辑空间等分成若干大小的页面，相应的把物理内存空间分成与页面大小的物理块，以页面为单位把进程空间装进物理内存中分散的物理块。
页面大小应该适中，过大难以分配，过小内存碎片过多，通常是512B~8K。
页表 记录进程逻辑空间于物理空间的映射
在页式存储管理， 页地址 = 页号 + 页内偏移
现代计算机系统中，可以支持非常大的逻辑 地址空间(2 32~2 64)，这样，页表就 变得非常大，要占用非常大的内存空间，如， 具有32位逻辑地址空间的分页系统，规定页 面大小为4KB，则在每个进程页表中的页表 项可达1M(2^20)个，如果每个页表项占用 1Byte，故每个进程仅仅页表就要占用1MB 的内存空间。
为了解决这个问题，引入了多级页表。
多级页表有一个根页表，每一个字块指向了内存中的一片空间，这块空间存储的是二级页表。以此类推，最后一级页表指向的字块才是进程实际使用的内存。通过这种分级机制，大大减少了进程中页表数占用的空间。
段式存储管理将进程逻辑空间划分成若干段(非等分），段的长度由连续逻辑的长度决定。
例如一个程序有主函数MAIN、子程序段X、子函数Y等，这个时候会根据每一个函数的逻辑长度来分配逻辑空间。
页表由 页号 和 基址 组成，但在段式存储管理中由于每一段的长度是不固定的，段表由 段号 、 基址 以及 段长 组成。
在段式存储管理， 段地址 = 段号 + 段内偏移
分页可以有效提高内存利用率(虽然说存在页内碎片)
分段可以更好满足用户需求
两者结合，形成段页式存储管理
先将逻辑空间按段式管理分成若干段，再把段内空间按页式管理等分成若干页。
在段页式存储管理中， 段页地址 = 段号 + 段内页号 + 页内地址
有些进程实际需要的内存很大，超过物理内存的容量。
由于操作系统的多道程序设计，使得每个进程可用物理内存更加稀缺。
不可能无限增加物理内存，物理内存总有不够的时候，于是便有了虚拟内存的概念。
虚拟内存是操作系统内存管理的关键技术，使得多道程序运行和大程序运行成为现实，她通过将进程所使用的内存进行划分，将部分暂时不使用的内存放置在辅存。
根据局部性原理，程序运行时，无需全部装入内存，装载部分即可。如果访问页不在内存，则发出缺页中断，发起页面置换。
从用户层面看，程序拥有很大的空间，即是虚拟内存。
虚拟内存实际是对物理内存的补充，速度接近于内存，成本接近于辅存。
置换算法一般有先进先出算法(FIFO)、最不经常使用算法(LFU)、最近最少使用算法(LRU)。
从计算机组成原理篇章中，我们可以知道，CPU的高速缓存没有数据时，需要从主存中加载数据。此时若主存中也没有数据，则需要从辅存中载入页面数据。
内存替换策略发生在Cache-主存层次、主存-辅存层次。Cache-主存层次的替换策略主要是为了解决 速度问题 ，
主存-辅存层次则。主要是为了解决 容量问题 。
顺序文件是指按顺序存放在存储介质中的文件，例如磁带的存储特性使得磁带文件只能存储顺序文件。
顺序文件是所有逻辑文件当中存储效率最高的。
可变长文件不适合使用顺序文件格式存储，索引文件是为了解决可变长文件存储而发明的一种文件格式，索引文件需要配合索引表完成存储的操作。
目录的层级结构是树状的，成为目录树。
目录树中任何文件或目录都只有唯一路径。
对CPU而言，凡是对CPU进行数据输入的都是输入设备，凡是CPU进行数据输出的都是输出设备。
缓冲区主要是解决CPU与IO设备的速率不匹配的问题，减少CPU处理IO请求的频率，提高CPU与IO设备之间的并行性。
专用缓冲区只适用于特定的IO进程，当这样的IO进程比较多时，对内存的消耗也很大，所以操作系统划出可供多个进程使用的公共缓冲区，称之为缓冲池。
SPOOLing技术是关于慢速字符设备如何与计算机主机交换信息的一种技术，利用高速共享设备将低速的独享设备模拟为高速的共享设备，逻辑上，系统为每一个用户都分配了一台独立的高速独享设备，是一种虚拟设备技术。
SPOOLing技术把同步调用低速设备改为异步调用。在输入、输出之间增加了排队转储环节(输入井、输出井)，SPOOLing负责输入(出)井与低速设备之间的调度，逻辑上，进程直接与高速设备交互，减少了进程的等待时间。
Ⅷ 操作系统概论索引文件组织是什么
如果学习孙枯了计算机软件专业的数档凯中据结构课程的话，可知索引文件本质上是一个链行山式存储结构（LinkList）。
Ⅸ UNIX操作系统，I字节索引结构。如图，可以解释的再通俗一点么，谢谢了!
1、UNIX文件系统采用多级索引结构,每个文件的索引表为13个索引项,每项2个字节.
2、前10个索引项直接存放文件信息的物理块号（直接寻址）,最多寻址10个物理块.
3、如果文件大于10块,则拆大乱利用第11项指向一个物理块,该块中最多可放256个文件物理块的块号（一次间接寻址）.
4、对于更大的文件可利用第12个索引项（二次间接寻址）,最多可寻址256*256个物理块.
5、再大的文仿祥件可以利用第13项作三次间接寻址,采用三级索引结构,文件最大可达256*256*256个物理块旅档.
对于2583个物理块的文件,用到二次间接寻址就可能满足了.
Ⅹ 操作系统有哪五大功能
操作系统的五大功能分别是处理器管理、存储器管理、设备管理、文件管理和作业管理。
1、处理器管理
处理器管理最基本的功能是处理中断事件，配置了操作系统后，就可对各种事件进行处理。处理器管理还有一个功能就是处理器调度，针对不同情况采取不同的调度策略。
2、存储器管理
存储器管理主要是指针对宴明内存储器的管理。主要任务是分配内存空间，保证各作业占用的存储空间不发生矛盾，并使各作业在自己所属存储区中不互相干扰。
3、设备管理
设备管理是指负责管理各类外围设备，包括分配、启动和故障处理等。主要任务是当用返祥漏户使用外部设备时，必须提漏烂出要求，待操作系统进行统一分配后方可使用。
4、文件管理
文件管理是指操作系统对信息资源的管理。在操作系统中，将负责存取的管理信息的部分称为文件系统。文件管理支持文件的存储、检索和修改等操作以及文件的保护功能。
5、作业管理
每个用户请求计算机系统完成的一个独立的操作称为作业。作业管理包括作业的输入和输出，作业的调度与控制，这是根据用户的需要来控制作业运行的。
