LSN
把記憶體中的BTree寫入檔案，就是要把BTree下面的Node（ValueNode，LeafNode和InterNode）都寫入檔案中，但是寫入檔案並不能直接把記憶體資料直接寫入檔案，比如指標或者引用。LeafNode和InterNode中有一個欄位或者成員變數：
//指向子節點的陣列 private Node[] childList = new Node[MAX_CHILDREN];這個欄位是指向節點的子節點引用，這個值是一個記憶體地址，直接寫入檔案以後，下次再讀出來以後，可能子節點已經不在這個記憶體值指向的記憶體位置了。所以，需要增加一個新的欄位：
//指向檔案中子節點的陣列 private long[] lsnList = new long[MAX_CHILDREN];這個欄位用於儲存每個子節點的LSN，LSN是檔案中的偏移地址（offset），當子節點寫入檔案以後，一定會有一個LSN，用於表示唯一標識該節點。這樣，當查詢子節點時，可以透過LSN來查詢子節點，不一定要用子節點引用。
Node序列化節點寫入檔案前，需要先序列化為可以寫入檔案的型別，一般為byte陣列型別，Java語言不能直接把記憶體物件轉換為byte陣列，需要專門處理（即使可以直接轉換成byte陣列，也不能直接轉換，因為有些欄位不能直接轉，比如子節點的指標）。
為了讓所有Node都能實現序列化，新增加一個介面，並且有一個需要實現的函式writeIntoBuffer：
public interface Loggable { void writeIntoBuffer(ByteBuffer buffer);}所有的節點都是實現這個介面：
//InterNode和TreeNode @Override public void writeIntoBuffer(ByteBuffer buffer) { buffer.putInt(count); for (int i=0; i<count; i++) { if (keyList[i] != DataItem.MAX_VALUE) { int size = keyList[i].getData().length; buffer.putInt(size); if (size != 0) { buffer.put(keyList[i].getData(), 0, size); } } else { buffer.putInt(-1); } } for (int i=0; i<count; i++) { buffer.putLong(lsnList[i]); }}//ValueNode @Override public void writeIntoBuffer(ByteBuffer buffer) { int size = 0; if (value != null) { size = value.getData().length; buffer.putInt(size); if (size != 0) { buffer.put(value.getData(), 0, size); } } else { buffer.putInt(size); }}引數buffer儲存Node序列化後的結果，這些結果通一個新類LogManager寫入到檔案中。
LogManager類LogManager是一個單例，這樣可以在任意需要的地方呼叫，LogManager中實現一個write方法或者函式，write可以將實現Loggable的物件寫入到檔案中。
檔案格式一個Loggable物件寫入檔案中需要一定的格式，不能隨意寫入，這樣才能保證能夠在需要這些物件時，成功從檔案中讀取出來。一般Loggable物件的檔案格式包括兩個部分：Header和Content，Header部分大小固定，Content部分每個不懂型別的Loggable都不相同（與TCP報文協議有點像）。Header包括兩個部分：Loggable在檔案中的大小以及型別；Content則是序列化後的Loggable物件。如下圖示：
LogHeaderHeader部分需要專門的類來處理：LogHeader。LogHeader主要有兩個欄位：LogType和LogSize，同時LogHeader也需要支援序列化。LogHeader還定義了各種不同型別的LogType，現在主要的LogType有ValueNode，LeafNode以及InterNode，所以LogHeader如下：
public class LogHeader { public final static int VALUE_NODE_LOG = 0; public final static int LEAF_NODE_LOG = 1;public final static int INTER_NODE_LOG = 2; private int logContentType; private int logContentSize; public LogHeader() { } public LogHeader(int logContentType, int logContentSize) { this.logContentType = logContentType; this.logContentSize = logContentSize; } public int getContentType() { return logContentType; } public int getContentSize() { return logContentSize; } public void writeIntoBuffer(ByteBuffer buffer) { buffer.putInt(logContentType); buffer.putInt(logContentSize); }}LogSize是節點寫入檔案以後的大小，這個大小和記憶體大小不一樣， 需要專門計算，TreeNode和ValueNode的計算方法如下：
//TreeNode計算LogSize @Override public int getLogSize() { int logSize = Integer.BYTES; for (int i=0; i<count; i++) { logSize += Integer.BYTES; if (keyList[i] != DataItem.MAX_VALUE) { logSize += keyList[i].getData().length; } } logSize += (count * Long.BYTES); return logSize;}//計算ValueNode的LogSize @Override public int getLogSize() { int logSize = Integer.BYTES; if (value != null) { logSize += value.getData().length; } return logSize; }LogHeader儲存的LogType需要每個Loggable提供，因此Loggable需要一個新的方法或者函式：getLogType。InterNode，LeafNode和ValueNode需要是這個函式，返回其型別。
1. 每個Node都一個固定的位置，這要求Node的LogSize必須固定，也就要求Node的記憶體大小也要固定，所以需要把記憶體劃分成一個個固定的Page或者Block，這樣可以Node可以寫入固定的位置，這個方法在很多傳統資料庫中會使用；
2. 還有一個方法就是每次寫入的Node都寫入檔案的尾部，這樣就不要求Node大小固定，同時這樣寫入的效能會更加好一些，這種方式成為Append-Only或者Log Structure Write，很多新興的儲存引擎使用這個方法，LSM也是使用這種方式寫入檔案。
本文中，我們選擇第二種方法，LogManager的write函式實現這個方法。
public long write(Loggable log) throws IOException { int logType = log.getLogType(); int logSize = log.getLogSize(); LogHeader logHeader = new LogHeader(logType,logSize); ByteBuffer buffer = ByteBuffer.allocate(logHeader.getLogSize() + logSize); logHeader.writeIntoBuffer(buffer); log.writeIntoBuffer(buffer); buffer.flip(); long lsn = fileChannel.size(); fileChannel.position(lsn); fileChannel.write(buffer); return lsn;}當程式關閉時，需要將所有的節點寫入檔案中，以便下次使用，Node的寫入就在BTree的close中實現。
寫入方法Node寫入之前需要寫入它的子節點，這是因為Node需要寫入子節點的LSN，而子節點只有寫入才有LSN，所以需要先寫入子節點。這個寫入方法就是後根寫入或者後序寫入，其過程如下：
為了實現這個方法，節點TreeNode需要增加一個新的方法writeChildren：
@Override public void writeChildren() { for (int i=0; i<count; i++) { try { if (childList[i] != null) { childList[i].writeChildren(); lsnList[i] = LogManager.getInstance().write(childList[i]); childList[i] = null; } } catch (IOException ex) { ex.printStackTrace(System.err); } }}ValueNode也需要實現一個空的writeChildren，因為ValueNode沒有子節點。
BTree的close方法則是先寫入根節點的子節點，然後寫入根節點：
public void close() throws IOException { if (root == null) { return; } root.writeChildren(); long newRootLSN = LogManager.getInstance().write(root); root = null;}實現從檔案中讀取BTree之前，需要先實現將Node從位元組陣列中反序列化，也就是實現Loggable中的readFromBuffer方法：
//TreeNode的readFromBuffer @Override public void readFromBuffer(ByteBuffer buffer) { count = buffer.getInt(); for (int i=0; i<count; i++) { int size = buffer.getInt(); if (size == 0) { keyList[i] = null; } else if(size == -1) { keyList[i] = DataItem.MAX_VALUE; } else { byte[] data = new byte[size]; buffer.get(data); keyList[i] = new DataItem(data); } } for (int i=0; i<count; i++) { lsnList[i] = buffer.getLong(); }}//ValueNode的readFromBuffer @Override public void readFromBuffer(ByteBuffer buffer) { int size = buffer.getInt(); if (size == 0) { value = null; } else { byte[] data = new byte[size]; buffer.get(data); value = new DataItem(data); }}LogHeader也需要實現一個readFromBuffer的方法：
public void readFromBuffer(ByteBuffer buffer) { logContentType = buffer.getInt(); logContentSize = buffer.getInt();}LogManager也需要一個支援透過LSN從檔案中讀取出Node的方法，其做法為根據LSN，跳轉到檔案對應的offset位置，然後先讀取固定大小的LogHeader，然後根據LogHeader中的LogType，建立一個對應的空Node，接著根據LogHeader中的LogSize讀取相同大小的位元組資料，然後使用readFromBuffer反序列化空的Node成為一個真正的Node：
public Node read(long lsn) throws IOException { LogHeader logHeader = new LogHeader(); ByteBuffer headerBuffer = ByteBuffer.allocate(logHeader.getLogSize()); fileChannel.position(lsn); fileChannel.read(headerBuffer); headerBuffer.flip(); logHeader.readFromBuffer(headerBuffer); ByteBuffer buffer = ByteBuffer.allocate(logHeader.getContentSize()); fileChannel.read(buffer); buffer.flip(); Node node; if (logHeader.getContentType() == LogHeader.VALUE_NODE_LOG) { node = new ValueNode(); } else if (logHeader.getContentType() == LogHeader.LEAF_NODE_LOG) { node = new LeafNode(); } else if (logHeader.getContentType() == LogHeader.INTER_NODE_LOG) { node = new InterNode(); } else { throw new RuntimeException("Invalid Log Type " + logHeader.getContentType()); } node.readFromBuffer(buffer); return node; }BTree的訪問都是從根節點開始的，所以讀取BTree需要先讀取根節點，才能進一步讀取其他節點。BTree所有節點都寫入檔案後，會有一個根節點的LSN，所以可以根據這個LSN來讀取根節點，但是如何儲存根節點LSN？有兩種方法：
人為的記錄LSN，這個方法不可取，因為程式是自動的，不能靠人工介入（當然今天很多看起來很自動的應用或者程式，後面都可能是人工介入的），另外人工記憶也不一定可靠將根節點LSN也寫入檔案，在需要的時候，掃描整個檔案取得LSN。本文選擇該方法。所以我們需要修改LogManager實現一個rootLSNWrite的方法以及BTree的close方法寫入rootLSN
public long writeRootLSN(long rootLSN) throws IOException { int logType = LogHeader.ROOT_LSN_LOG; int logSize = Long.BYTES; LogHeader logHeader = new LogHeader(logType,logSize); ByteBuffer buffer = ByteBuffer.allocate(logHeader.getLogSize() + logSize); logHeader.writeIntoBuffer(buffer); buffer.putLong(rootLSN); buffer.flip(); long lsn = fileChannel.size(); fileChannel.position(lsn); fileChannel.write(buffer); return lsn;} public void close() throws IOException { if (root == null) { return; } root.writeChildren(); long newRootLSN = LogManager.getInstance().write(root); root = null; if (newRootLSN != rootLSN) { rootLSN = newRootLSN; LogManager.getInstance().writeRootLSN(rootLSN); }}讀取BTree之前需要讀取根節點LSN，而此時沒有任何的LSN資訊，所以需要從頭到尾掃描整個檔案，找到最後一個LOG型別為ROOT_LSN_LOG的記錄，然後從其中讀取根節點LSN，這個操作需要BTree的構造方法中執行：
public long readRootLSN() throws IOException { long rootLSN = -1; long readLSN = 0; LogHeader logHeader = new LogHeader(); ByteBuffer headerBuffer = ByteBuffer.allocate(logHeader.getLogSize()); fileChannel.position(readLSN); int readBytes = fileChannel.read(headerBuffer); while(readBytes > 0) { headerBuffer.flip(); logHeader.readFromBuffer(headerBuffer); if (logHeader.getContentType() == LogHeader.ROOT_LSN_LOG) { ByteBuffer buffer = ByteBuffer.allocate(logHeader.getContentSize()); fileChannel.read(buffer); buffer.flip(); rootLSN = buffer.getLong(); System.out.println("Root LSN(Read): " + rootLSN + ", LSN: " + readLSN); } readLSN += (logHeader.getLogSize() + logHeader.getContentSize()); fileChannel.position(readLSN); headerBuffer.clear(); readBytes = fileChannel.read(headerBuffer); } return rootLSN;}以前子節點可以直接透過childList[i]獲取，現在不能使用這種方式，因為childList[i]可能是空的，需要其他方法實現，實現的方式是先判斷childList[i]是否為空，如果不為空返回該值，如果為空，根據lsnList[i]從檔案中讀取該節點:
protected Node getChild(int index) { synchronized(this) { if (childList[index] == null) { try { childList[index] = LogManager.getInstance().read(lsnList[index]); } catch (IOException ex) { ex.printStackTrace(System.err); } } return childList[index]; }}BTree還需要一些修改，在put方法中，發現rootNode為空，而且rootLSN不為-1是，需要從檔案中讀取rootNode，而不是新建一個：
if (root == null) { if (rootLSN == -1) { root = new LeafNode(); } else { try { root = (TreeNode) LogManager.getInstance().read(rootLSN); } catch (IOException ex) { ex.printStackTrace(System.err); } } }在delete以及get方法中，如果rootNode為空，且rootLSN不為空，則需要從檔案中讀取該節點：
if (root == null) { if (rootLSN == -1) { treeLocker.readLock().unlock(); return null; } else { try { root = (TreeNode) LogManager.getInstance().read(rootLSN); } catch (IOException ex) { ex.printStackTrace(System.err); } } }根據上面的討論，我們可以實現一個支援讀寫檔案的BTree，但是這個實現有一個問題，就是每次關閉BTree時，所有的節點都會重新寫入檔案，即使沒有做任何修改。這樣是比較浪費硬碟空間，需要最佳化一下。首先我們做一個定義，所有不是從檔案中讀取的Node都為dirty的，包括新建立的Node, 任何讀寫操作，修改count，keyList以及lsnList都需要設定Node為Dirty；Dirty的Node才需要寫入檔案，非dirty的node不用寫入檔案。這樣writeChildren方法需要做一些修改：
@Override public void writeChildren() { for (int i=0; i<count; i++) { try { if (childList[i] != null && childList[i].isDirty()) { childList[i].writeChildren(); lsnList[i] = LogManager.getInstance().write(childList[i]); childList[i] = null; setDirty(true); } } catch (IOException ex) { ex.printStackTrace(System.err); } }}略
結論本文討論瞭如何把BTree寫入檔案中，實現了記憶體資料保留的方法，同時也介紹瞭如何讀取這些資料，特別是RootLSN，這樣就實現了一個基於檔案的BTree，但是記憶體是有限的，不可能在所有情況一下，記憶體都足以支援BTree從容呼叫close方法，把所有的dirty資料都寫入檔案中，下篇文章，我們將討論如何處理這種記憶體不夠的情況。