----《大規模分布式存儲系統：原了解析與架構實戰》讀書筆記
這篇依然是學習《大規模分布式存儲系統：原了解析與架構實戰》一書之外的一個話題。通過學習本書，知道了分布式鍵值系統，通常使用sstable(一個無序的鍵值對集合容器)作為其磁盤上的布局。這不禁讓人産生聯想，傳統資料庫使用的是什麼存儲布局來存儲資料呢？這就是今天要探讨的主題----heapfile.
heapfile是一種儲存page資料的資料結構，類似于連結清單，heapfile也是一種無序容器。
heapfile和sstable其實都是具有特殊結構的檔案。既然都是儲存資料，為什麼不直接使用檔案呢？因為系統檔案并不區分檔案的内容。處理起來粒度大。而heapfile和sstable都能夠提供記錄級别的管理，從這一點上來說，二者的功能都是相同的，都是為系統提供更細粒度的存儲管理。
基本上，oracle,mysql,postgresql，sqlserver等傳統資料庫都使用heapfile作為其存儲布局管理。如同sstable一樣，heapfile的結構實際很簡單，但是你需要時刻知道，資料庫中存儲使用的是heapfile。
我們都知道，資料庫通常使用b+樹作為索引，但是國内很少有人提到資料庫使用的是heapfile來管理記錄的存儲。國外的一些大學在“資料庫系統實作”這門課上通常會讓學生實作一個簡單的資料庫，是以有不少heapfile的資料。
采用連結清單形式的是heapfile如下：
heap file和連結清單結構類似的地方：
支援增加（append）功能
支援大規模順序掃描
不支援随機通路
這種方式的heapfile在尋找具有合适空間的半空page時需要周遊多個頁，i/o開銷大。是以一般常用的是采用基于索引的heafile.在heapfile中使用一部分空間來存儲page作為索引，并記錄對應page的剩餘量。如下：
像上圖那樣，索引單獨存在一個page上。資料記錄存在其他page上，如果有多個索引的page，則可以表示為：
下面是heap file自有的一些特性：
資料儲存在二級存儲體（disk）中：heapfile主要被設計用來高效存儲大資料量，資料量的大小隻受存儲體容量限制；
heapfile可以跨越多個磁盤空間或機器：heapfile可以用大位址結構去辨別多個磁盤，甚至于多個網絡；
資料被組織成頁；
頁可以部分為空（并不要求每個page必須裝滿）；
頁面可以被分割在某個存儲體的不同的實體區域，也可以分布在不同的存儲體上，甚至是不同的網絡節點中。我們可以簡單假設每一個page都有一個唯一的位址辨別符pageaddress，并且作業系統可以根據pageaddress為我們定位該page。
一般情況下，使用page在其所在檔案中的偏移量就可以表示了。
在實作資料在檔案中的布局的時候，為了實作更簡單，我先做了一個簡單的約定：一個檔案表示一個關系。
這意味着一個關系的記錄的條數受到檔案系統的限制，如果是fat32位系統，一個檔案最大隻能是4g，如果是普通的etx3,單個檔案則是2tb。
同樣為了實作簡單，采用了數組的方式來組織頁。
heapfile的組織如下：
其中n和p為檔案的最開始的16(或32)個位元組。即n和p實際儲存的是兩個long型的值。n表示檔案中頁的數目，p表示每頁的大小。則：
檔案的總大小 <code>filesize = n * p + 2 * sizoeof(long)</code>.
任意一頁的頁首位址 <code>page(k) = p * ( k - 1 ) +2 * sizeof(long) (k = 1,2,...,n)</code>
頁中可以包含多條記錄。如果每天記錄的長度都相同，則稱為定長記錄，如果每條記錄的長度有不相同，則稱為變長記錄。定長記錄可以采用數組的方式記錄，但是變長記錄不行。是以采用偏移量的方式來記錄。page的布局如下：
從頁首開始一條條記錄。頁尾用一個int整形記錄剩餘空間的偏移量，再用一個int整形該頁已存儲的記錄數，每一條記錄在頁中的偏移量和是否被删除的标記。
其中，
freespace表示該頁空間剩餘量的首位址，也是最後一條記錄的尾位址+1；
n表示該頁中已經存在的記錄的條數，包括哪些被标記為删除的記錄；
尾部的r1,r2,..表示其對應記錄在頁内的偏移位址，同時還會分出1個bit位标記這條記錄是否被删除。如果要支援記錄跨頁存儲的話，還需要再分出2bit來标記其是否是跨頁的記錄。
尾部的r1，r2等可以定義為如下結構體：
indexrecord總共為32bit，其中29bit表示記錄的頁内偏移位址 ; 1bit表示記錄是否被删除 ; 2bit表示是否跨頁存儲，0x00表示不跨頁，0x01表示跨頁，記錄為開始的部分，0x10表示跨頁，記錄為中間部分，中間部分可以有多條，0x11表示跨頁，記錄為結尾的部分。
則：
任意一條記錄的indexrecord首位址為 <code>r(k) = p-(2+k)*sizeof(int); (k=1,2,..,n)</code>
計算一個頁還能容納的長度為 <code>freelength = p-(2+n)*sizeof(int)</code>
判斷一個頁是否裝滿的條件為 <code>freelength > 0</code>
一個page通常的大小為2k，4k,8k,16k等。
這裡還要再提下空隙的問題，同時删除記錄時直接采用标記法，但是當更新記錄的時候，由于是變長記錄。存在以下3種情況：
新記錄和原記錄一樣長：原處更新記錄即可
新紀錄比原記錄長：原記錄标記删除，并新增一條記錄，如果有索引，更新索引檔案。
新紀錄變原記錄短：原處更新記錄，無需更新索引檔案，但是出現了記錄的空隙。
當空間緊張時，可以嘗試壓縮頁，剔除其中的空隙。
定長記錄的布局可以比較簡單，此處不提。本節主要讨論變長記錄的布局,也叫記錄的序列化。
一個常見的例子為給定表person的定義，使name可以是不超過1024個字元。schema如下：
上面表的記錄是變長的原因為：
name字段是一個變長的字元串；
birthdate可以為null；
變長record的序列化的關鍵是字段邊界的界定。一種比較流行的方法是在record的首部儲存字段邊界的offset。
person的record的編排方式如下：
note：我們在首部設定4個整型去存儲三個字段的四個邊界offset。
上面的編排方式很自然的提供一種null字段的編排方式--可以辨別該字段的值為null，如下圖：
第三個offset和第四個offset指向同一個位置，那麼就表明第三個字段的大小是零，即是一個null值。
可以看到，使用偏移量無論是page的布局，還是記錄的序列化，都是非常友善的。
根據以上介紹， 可以有以下推斷：
記錄的總長度 <code>recordlength = r[k] k為字段數</code>
每個字段的長度為 <code>colnumlength(k) = r[k] - r[k-1] , (k=1,2,3,...)</code>
判斷一個字段是否為null <code>colnumlength[k] = 0 ,(k=1,2,3,...)</code>
最後我們在來看一遍關系person的heapfile檔案的整體布局圖