在ehcache中，如果設定了overflowtodisk屬性，當cache中的資料超過限制時，ehcache會根據配置的溢出算法（先進先出（fifo）、最近最少使用算法（lru）等），選擇部分執行個體，将這些執行個體的資料寫入到磁盤檔案中臨時存儲，已減少記憶體的負擔，當記憶體中的執行個體數減少（因為逾時或手工移除）或某些執行個體被使用到時，又可以将這些寫入磁盤的資料重新加載到記憶體中。這個過程包含執行個體的序列化和反序列化，以及對磁盤檔案不同區域的讀寫管理，這篇文章主要關注于磁盤檔案不同區域的讀寫管理。
需求思考
當cache系統發現需要溢出某些執行個體到磁盤時，它需要把執行個體序列化後，将序列化後的二進制資料寫入磁盤，并釋放記憶體中的資料；當使用者請求讀取已經溢出到磁盤中的執行個體時，需要讀取磁盤中的二進制資料，反序列化成記憶體執行個體，傳回給使用者，由于該執行個體最近一次被通路，因而根據程式的局部性（或許這裡是資料的局部性）原理，cache會将新讀取的執行個體儲存在記憶體中，并釋放是磁盤中占用的空間；如果此時或者在将來的某個時候記憶體依然或變的非常緊張，cache系統會根據溢出算法溢出根據算法得到的執行個體到磁盤，因而這裡磁盤的讀寫是一個動态的、周而複始的行為。在把序列化的執行個體寫入磁盤時，我們需要配置設定相同大小的磁盤空間，并紀錄該執行個體的key、在磁盤檔案中的起始位置、資料大小用于在後來的讀回資料并反序列化成記憶體執行個體；當一個執行個體資料被讀回記憶體時，需要釋放它在磁盤中占用的記憶體，進而可以将它原本占用磁盤配置設定給其他溢出執行個體。這有點類似記憶體管理的味道：對一台機器來說，記憶體大小是有限的，而程序不斷的産生、銷毀，在啟動一個程序時，需要為該程序配置設定一定的初始空間，并且随着程序的運作，需要不斷的為其配置設定運作期間增長的記憶體空間；當一個程序銷毀時，作業系統需要回收配置設定給它的空間，以實作循環利用。在作業系統中，記憶體管理方式有：
1. 固定分區配置設定，作業系統把記憶體分成固定大小的相等的或不等的記憶體分區，每個程序隻能配置設定給這幾個固定大小的分區。這是一種最簡單的記憶體管理算法，它需要提前直到一個程序最大會使用的記憶體大小，并且需要合理配置設定記憶體分區的大小，以防止有些程序因為使用記憶體過多而找不到對應大小的空閑分區而無法載入，雖然此時可能記憶體還有很多其他比較小的空閑分區，它也要防止記憶體分區過大，進而在載入過小程序時浪費記憶體。對這種記憶體管理方式，隻需要一張分區表即可，每個表項紀錄了分區号、起始位置、大小、配置設定狀态等。如果表項不多，可以直接用數組表示，實作簡單，查找效率影響也不大，如果表項很多，則可以考慮在其上層建立一顆空閑分區紅黑樹，已提升查找、插入、删除效率。
2. 相對于固定分區配置設定，自然會存在動态記憶體配置設定，已處理不同記憶體需要不同大小的記憶體的需求，即作業系統根據不同程序所需的不同記憶體大小配置設定記憶體。可以使用三種資料結構來管理分區：空閑分區表、空閑分區鍊以及空閑分區紅黑樹，對于空閑分區表和空閑分區紅黑樹，每一個節點都紀錄了空閑分區号、起始位置、大小等，不同的是分區表組成一個數組，而空閑分區紅黑樹組成一顆樹已提升查找、插入、删除等性能，對空閑分區鍊，它不象空閑分區表和空閑分區紅黑樹，使用額外的記憶體中間存儲資訊，它直接使用在空閑記憶體的頭和尾存儲額外的分區鍊資訊。而對分區配置設定算法，可以使用：首次适應算法、循環首次适應算法、最佳适應算法、最壞适應算法等。在配置設定記憶體時，首先根據一定的算法找到可以裝載該程序的空閑分區，然後根據目前分區的大小和程序所需要的記憶體大小以及最小可存在的記憶體分區的大小（防止過多的過小的記憶體碎片産生）選擇将目前空閑分區的部分分區劃分給該新程序或将目前整個分區配置設定給新程序，如果隻是将目前空閑分區的部分分區劃分給新程序，隻需調整目前空閑分區項的基本資訊即可，否則需要将該空閑程序節點從空閑分區表、鍊、樹中移除。記憶體回首時，根據不同的算法将該記憶體區建立出一個空閑分區節點，将它插入到原有空閑分區表、鍊、樹中，在插入前，如果出現相鄰的空閑分區表，則需要将所有的相鄰空閑分區合并。
3. 夥伴系統。
4. 可重定位分區配置設定。
貌似有點離題了，作為cache的溢出資料磁盤檔案管理為了簡單和效率的考慮，不會也沒必要象記憶體管理一樣實作的那麼複雜，因而夥伴系統和可重定為分區配置設定不細講了，需要進一步了解的可以參考任意一本的作業系統教材。其實cache的溢出資料磁盤檔案管理更類似于記憶體溢出到磁盤的交換區管理，即作業系統會将暫時不用的程序或資料調換到外存中，已騰出記憶體供其他需要程序使用，已提升記憶體使用率。一般程序或記憶體交換出的資料在交換區中的停留時間比較段，而交換操作又比較頻繁，因而交換區中的空間管理主要為了提高程序或資料換入和換出的速度，為此，一般采用的是連續配置設定方式，較少考慮外存碎片的問題，而對其管理的資料結構和上述的資料結構類似，不再贅述。
ehcache使用aa tree資料結構來管理磁盤空間
在ehcache中，采用aa tree資料結構來紀錄空閑磁盤塊，因而首先了解一下aa tree的實作（aatreeset類）。aa tree出自arne andersson在1993年的論文“balanced search trees made simple”中提出的對紅黑樹的改進，因而它是紅黑樹的變種，但是比紅黑樹實作要簡單。不同于紅黑樹采用顔色（紅色或黑色）來紀錄一個節點的狀态以調整節點的位置來保持其平衡性，aa tree采用level值來紀錄目前節點的狀态以保持它的平衡性，level值相當于紅黑樹中的黑節點高度。aa tree的定義如下：
1. aa tree是紅黑樹的變種，因而它也是一顆二叉排序樹。
2. 每個葉子節點的level是1。
3. 每個左孩子的level是其父節點level值減1。
4. 每個右孩子的level和其父節點的level相等或是其父節點的level減1。
5. 每個右孫子的level一定比其祖父節點的level要小。
6. 每個level大于1的節點有兩個孩子。
類似紅黑樹，aa tree通過對level值的判斷來調整節點位置以保證目前tree維持以上定義。由于aa tree采用level來紀錄每個節點的狀态，并且每個右孩子的level和其父節點的level值相等或是其父節點的level減1，因而一般aa tree采用如下方式表達（圖檔來自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：
根據以上aa tree的定義，aa tree禁止以下兩種情況的出現：
1. 禁止出現連續兩個水準方向鍊（horizontal link），所謂horizontal link是指一個結點跟它的右孩子結點的level相同（左孩子結點永遠比它的父結點level小1）。這個規定其實相當于rb樹中不能出現兩個連續的紅色結點。即需要滿足定義5。
2. 禁止出現向左的水準方向鍊（left horizontal link），也就是說一個結點最多隻能出現一次向右的水準方向鍊。在aa tree中水準鍊相當于紅黑樹中的紅孩子，根據定義3，aa tree不允許左孩子出現“紅節點”，即aa tree的左孩子的level值總是要比父節點的level值小1。
對不允許的情況如下圖所示（圖檔同樣來自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：
aa tree的節點調整
在aa tree中，隻需要當出現以上禁止的兩種情況下才需要調整，因而它比紅黑樹的邏輯要簡單的多。同紅黑樹，aa tree也通過旋轉節點來調整節點以使目前樹始終保持aa tree的特點，然而aa tree建立了自己的術語：skew和split。skew用于處理出現向左的水準方向鍊的情況；split用于處理連續兩個水準方向鍊的情況。
skew相當于一個右旋操作：
private static <t> node<t> skew(node<t> top) {
if (top.getleft().getlevel() == top.getlevel() && top.getlevel() != 0) {
node<t> save = top.getleft();
top.setleft(save.getright());
save.setright(top);
top = save;
}
return top;
}
split相當于一個左旋操作，并且它還會使父節點的level加1：
private static <t> node<t> split(node<t> top) {
if (top.getright().getright().getlevel() == top.getlevel() && top.getlevel() != 0) {
node<t> save = top.getright();
top.setright(save.getleft());
save.setleft(top);
top.incrementlevel();
當skew之前已經有一個右孩子的level跟目前結點的level相同，skew 操作之後可能引起兩個連續水準方向鍊，這時需要配合使用split操作。split操作會新的子樹的根節點level增加1（原節點的右孩子），當原節點作為其父結點的右孩子而且其父結點跟祖父結點的level相同時，在split操作後會引起兩個連續水準方向鍊，此時需要進一步的split操作，而當原節點作為其父節點的左孩子時，在split操作後會引起向左方向的水準鍊，此時需要配合使用skew操作；因而aa tree在做調整時，需要skew和split一起配合操作。
aa tree節點定義
aa tree節點定義和紅黑樹節點定義類似，隻是它沒有了color字段，而使用level字段替代。在ehcache中采用node接口表達，在該接口中它還定義了compare()方法以比較兩個節點之間的大小關系：
public static interface node<e> {
public int compareto(e data);
public void setleft(node<e> node);
public void setright(node<e> node);
public node<e> getleft();
public node<e> getright();
public int getlevel();
public void setlevel(int value);
public int decrementlevel();
public int incrementlevel();
public void swappayload(node<e> with);
public e getpayload();
對該接口的實作也比較簡單：
public abstract static class abstracttreenode<e> implements node<e> {
private node<e> left;
private node<e> right;
private int level;
.....
private static final class treenode<e extends comparable> extends abstracttreenode<e> {
private e payload;
public void swappayload(node<e> node) {
if (node instanceof treenode<?>) {
treenode<e> treenode = (treenode<e>) node;
e temp = treenode.payload;
treenode.payload = this.payload;
this.payload = temp;
} else {
throw new illegalargumentexception();
}
}
aa tree的插入操作
同紅黑樹，作為一顆二叉排序樹，aa tree先以二叉排序樹的算法插入一個新節點，然後對插入的節點做skew和split調整，以維持aa tree的定義，它是一個遞歸操作，因而可以保證在目前一次調整完成後還需要再調整時，在上一個遞歸棧中可以繼續調整（這裡比較使用目前節點和傳入資料做比較，因而當direction大于0時表示目前節點要比傳入資料大，因而應該插入它的左子樹，我剛開始沒仔細看，還以為這是一顆倒序樹，囧。。。。）：
private node<t> insert(node<t> top, t data) {
if (top == terminal()) {
mutated = true;
return createnode(data);
} else {
int direction = top.compareto(data);
if (direction > 0) {
top.setleft(insert(top.getleft(), data));
} else if (direction < 0) {
top.setright(insert(top.getright(), data));
return top;
top = skew(top);
top = split(top);
return top;
aa tree的删除操作
aa tree節點的删除也隻需考慮兩種情況：
1. 如果删除節點的後繼節點不是葉子節點，将後繼節點的值賦給目前節點，後繼節點右孩子的值賦給後繼節點，删除後繼節點。
如下圖，要删除30，其後繼節點是35，删除時，将30和35節點交換，将35和40節點交換，後删除40節點（以下圖檔都出自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：
2. 如果删除節點的後繼節點是葉子節點，後繼節點的值賦給目前節點，并将後繼節點的父節點level值減1，如果出現向左的水準鍊或向右的連續水準鍊，則做skew和split調整。
如下面兩圖分别為删除50節點和删除15節點的事例圖：
ehcache aatreeset中删除的代碼（這裡的比較也是使用目前節點和傳入資料比較，因而當direction大于0時，應該向左走，要特别留意）：
private node<t> remove(node<t> top, t data) {
if (top != terminal()) {
heir = top;
top.setleft(remove(top.getleft(), data));
item = top;
top.setright(remove(top.getright(), data));
if (top == heir) {
if (item != terminal() && item.compareto(data) == 0) {
mutated = true;
item.swappayload(top);
removed = top.getpayload();
top = top.getright();
}
if (top.getleft().getlevel() < top.getlevel() - 1 || top.getright().getlevel() < top.getlevel() - 1) {
if (top.getright().getlevel() > top.decrementlevel()) {
top.getright().setlevel(top.getlevel());
}
top = skew(top);
top.setright(skew(top.getright()));
top.getright().setright(skew(top.getright().getright()));
top = split(top);
top.setright(split(top.getright()));
參考文章：
http://blog.csdn.net/zhaojinjia/article/details/8121156
http://www.cnblogs.com/ljsspace/archive/2011/06/16/2082240.html
http://baike.baidu.com/view/10841337.htm