Ⅰ 程序員必備知識（操作系統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、作業管理
每個用戶請求計算機系統完成的一個獨立的操作稱為作業。作業管理包括作業的輸入和輸出，作業的調度與控制，這是根據用戶的需要來控製作業運行的。
