小型單文件NoSQL數據庫SharpFileDB初步實現
我不是數據庫方面的專家，不過還是想做一個小型的數據庫，算是一種通過mission impossible進行學習鍛煉的方式。我知道這是自不量力，不過還是希望各路大神批評的時候不要人身攻擊，謝謝。
SharpFileDB
最近所做的多文件數據庫是受（C#實現文件數據庫）的啟發。后來又發現了（LiteDB），看到了單文件數據庫和分頁、索引、查詢語句等的實現方式，大受啟發。不過我仍舊認為LiteDB使用起來有些不順暢，它的代碼組織也不敢完全茍同。所以，我重新設計了一個小型的單文件數據庫SharpFileDB：
無需配置服務器。
無需SQL。
100%純C#開發的一個不到50KB的DLL。
支持事務ACID。
寫入失敗后可恢復（日志模式）。
可存儲任意繼承了Table且具有[Serializable]特性的類型（相當于關系數據庫的Table）。類型數目不限。
可存儲System.Drawing.Image等大型對象。
單文件存儲，只要你的硬盤空間夠大，理論上能支持的最大長度為long.MaxValue = 9223372036854775807 = 0x7FFFFFFFFFFFFFFF = 8589934591GB = 8388607TB = 8191PB = 7EB的大文件。
每個類型都可以建立多個索引，索引數目不限。只需在屬性上加[TableIndex]特性即可實現。
支持通過Lambda表達式進行查詢。
開源免費，2300行代碼，1000行注釋。
附帶Demo、可視化的監視工具、可視化的數據庫設計器，便于學習、調試和應用。
使用場景
假設已經做好了這樣一個單文件數據庫，我期望的使用方式是這樣的：
1 string fullname = Path.Combine(Environment.CurrentDirectory, "test.db"); 2 using (FileDBContext db = new FileDBContext(fullname)) 3 { 4 Cat cat = new Cat(); 5 string name = "kitty " + random.Next(); 6 cat.KittyName = name; 7 cat.Price = random.Next(1, 100); 8 9 db.Insert(cat); 10 11 System.Linq.Expressions.Expression<Func<Cat, bool>> pre = null; 12 13 pre = (x => 14 (x.KittyName == "kitty" || (x.KittyName == name && x.Id.ToString() != string.Empty)) 15 || (x.KittyName.Contains("kitty") && x.Price > 10) 16 ); 17 18 IEnumerable<Cat> cats = db.Find<Cat>(pre); 19 20 cats = db.FindAll<Cat>(); 21 22 cat.KittyName = "小白 " + random.Next(); 23 db.Update(cat); 24 25 db.Delete(cat); 26 }
就像關系型數據庫一樣，我們可以創建各種Table（例如這里的Cat）。然后直接使用Insert(Table record);插入一條記錄。創建自定義Table只需繼承Table實現自己的class即可。
1 /// <summary> 2 /// 繼承此類型以實現您需要的Table。 3 /// </summary> 4 [Serializable] 5 public abstract class Table : ISerializable 6 { 7 8 /// <summary> 9 /// 用以區分每個Table的每條記錄。 10 /// This Id is used for diffrentiate instances of 'table's. 11 /// </summary> 12 [TableIndex]// 標記為索引，這是每個表都有的主鍵。 13 public ObjectId Id { get; internal set; } 14 15 /// <summary> 16 /// 創建一個文件對象，在用<code>FileDBContext.Insert();</code>將此對象保存到數據庫之前，此對象的Id為null。 17 /// </summary> 18 public Table() { } 19 20 /// <summary> 21 /// 顯示此條記錄的Id。 22 /// </summary> 23 /// <returns></returns> 24 public override string ToString() 25 { 26 return string.Format("Id: {0}", this.Id); 27 } 28 29 /// <summary> 30 /// 使用的字符越少，序列化時占用的字節就越少。一個字符都不用最好。 31 /// <para>Using less chars means less bytes after serialization. And "" is allowed.</para> 32 /// </summary> 33 const string strId = ""; 34 35 #region ISerializable 成員 36 37 /// <summary> 38 /// This method will be invoked automatically when IFormatter.Serialize() is called. 39 /// <para>You must use <code>base(info, context);</code> in the derived class to feed <see cref="Table"/>'s fields and properties.</para> 40 /// <para>當使用IFormatter.Serialize()時會自動調用此方法。</para> 41 /// <para>繼承此類型時，必須在子類型中用<code>base(info, context);</code>來填充<see cref="Table"/>自身的數據。</para> 42 /// </summary> 43 /// <param name="info"></param> 44 /// <param name="context"></param> 45 public virtual void GetObjectData(SerializationInfo info, StreamingContext context) 46 { 47 byte[] value = this.Id.Value;//byte[]比this.Id.ToString()占用的字節少2個字節。 48 info.AddValue(strId, value); 49 } 50 51 #endregion 52 53 /// <summary> 54 /// This method will be invoked automatically when IFormatter.Serialize() is called. 55 /// <para>You must use <code>: base(info, context)</code> in the derived class to feed <see cref="Table"/>'s fields and properties.</para> 56 /// <para>當使用IFormatter.Serialize()時會自動調用此方法。</para> 57 /// <para>繼承此類型時，必須在子類型中用<code>: base(info, context)</code>來填充<see cref="Table"/>自身的數據。</para> 58 /// </summary> 59 /// <param name="info"></param> 60 /// <param name="context"></param> 61 protected Table(SerializationInfo info, StreamingContext context) 62 { 63 byte[] value = (byte[])info.GetValue(strId, typeof(byte[])); 64 this.Id = new ObjectId(value); 65 } 66 67 }
這里的Cat定義如下：
1 [Serializable] 2 public class Cat : Table 3 { 4 /// <summary> 5 /// 顯示此對象的信息，便于調試。 6 /// </summary> 7 /// <returns></returns> 8 public override string ToString() 9 { 10 return string.Format("{0}: ￥{1}", KittyName, Price); 11 } 12 13 public string KittyName { get; set; } 14 15 public int Price { get; set; } 16 17 public Cat() { } 18 19 const string strKittyName = "N"; 20 const string strPrice = "P"; 21 22 public override void GetObjectData(System.Runtime.Serialization.SerializationInfo info, System.Runtime.Serialization.StreamingContext context) 23 { 24 base.GetObjectData(info, context); 25 26 info.AddValue(strKittyName, this.KittyName); 27 info.AddValue(strPrice, this.Price); 28 } 29 30 protected Cat(System.Runtime.Serialization.SerializationInfo info, System.Runtime.Serialization.StreamingContext context) 31 : base(info, context) 32 { 33 this.KittyName = info.GetString(strKittyName); 34 this.Price = info.GetInt32(strPrice); 35 } 36 37 }
后面我提供了一個可視化的數據庫設計器，你可以像在SQL Server Management里那樣設計好你需要的表，即可一鍵生成相應的數據庫項目源碼。
從何開始
用C#做一個小型單文件數據庫，需要用到.NET Framework提供的這幾個類型。
FileStream
文件流用于操作數據庫文件。FileStream支持隨機讀寫，并且FileStream.Length屬性是long型的，就是說數據庫文件最大可以有long.MaxValue個字節，這是超級大的。
使用FileStream的方式是這樣的：
1 var fileStream = new FileStream(fullname, FileMode.Open, FileAccess.ReadWrite, FileShare.Read);
這句代碼指明：
fullname：打開絕對路徑為fullname的文件。
FileMode.Open：如果文件不存在，拋出異常。
FileAccess.ReadWrite：fileStream對象具有讀和寫文件的權限。
FileShare.Read：其它進程只能讀此文件，不能寫。我們可以用其它進程來實現容災備份之類的操作。
BinaryFormatter
讀寫數據庫文件實際上就是反序列化和序列化對象的過程。我在這里詳細分析了為什么使用BinaryFormatter。
聯合使用FileStream和BinaryFormatter就可以實現操作數據庫文件的最基礎的功能。
1 /// <summary> 2 /// 使用FileStream和BinaryFormatter做單文件數據庫的核心工作流。 3 /// </summary> 4 /// <param name="fullname"></param> 5 public static void TypicalScene(string fullname) 6 { 7 // 初始化。 8 BinaryFormatter formatter = new BinaryFormatter(); 9 10 // 打開數據庫文件。 11 FileStream fs = new FileStream(fullname, FileMode.Open, FileAccess.ReadWrite, FileShare.Read); 12 13 // 把對象寫入數據庫。 14 long position = 0;// 指定位置。 15 fs.Seek(position, SeekOrigin.Begin); 16 Object obj = new Object();// 此處可以是任意具有[Serializable]特性的類型。 17 formatter.Serialize(fs, obj);// 把對象序列化并寫入文件。 18 19 fs.Flush(); 20 21 // 從數據庫文件讀取對象。 22 fs.Seek(position, SeekOrigin.Begin);// 指定位置。 23 Object deserialized = formatter.Deserialize(fs);// 從文件得到反序列化的對象。 24 25 // 關閉文件流，退出數據庫。 26 fs.Close(); 27 fs.Dispose(); 28 }
簡單來說，這就是整個單文件數據庫最基本的工作過程。后續的所有設計，目的都在于得到應指定的位置和應讀寫的對象類型了。能夠在合適的位置寫入合適的內容，能夠通過索引實現快速定位和獲取/刪除指定的內容，這就是實現單文件數據庫要做的第一步。能夠實現事務和恢復機制，就是第二步。
MemoryStream
使用MemoryStream是為了先把對象轉換成byte[]，這樣就可以計算其序列化后的長度，然后才能為其安排存儲到數據庫文件的什么地方。
1 /// <summary> 2 /// 把Table的一條記錄轉換為字節數組。這個字節數組應該保存到Data頁。 3 /// </summary> 4 /// <param name="table"></param> 5 /// <returns></returns> 6 [MethodImpl(MethodImplOptions.AggressiveInlining)] 7 public static byte[] ToBytes(this Table table) 8 { 9 byte[] result; 10 using (MemoryStream ms = new MemoryStream()) 11 { 12 Consts.formatter.Serialize(ms, table); 13 if (ms.Length > (long)int.MaxValue)// RULE: 一條記錄序列化后最長不能超過int.MaxValue個字節。 14 { throw new Exception(string.Format("Toooo long is the [{0}]", table)); } 15 result = new byte[ms.Length]; 16 ms.Seek(0, SeekOrigin.Begin); 17 ms.Read(result, 0, result.Length); 18 } 19 20 return result; 21 }
準備知識
全局唯一編號
寫入數據庫的每一條記錄，都應該有一個全局唯一的編號。（C#實現文件數據庫）和（LiteDB）都有一個ObjectId類型，兩者也十分相似，且存儲它需要的長度也小于.NET Framework自帶的Guid，所以就用ObjectId做全局唯一的編號了。
1 /// <summary> 2 /// 用于生成唯一的<see cref="Table"/>編號。 3 /// </summary> 4 [Serializable] 5 public sealed class ObjectId : ISerializable, IComparable<ObjectId>, IComparable 6 { 7 private string _string; 8 9 private ObjectId() 10 { 11 } 12 13 internal ObjectId(string value) 14 : this(DecodeHex(value)) 15 { 16 } 17 18 internal ObjectId(byte[] value) 19 { 20 Value = value; 21 } 22 23 internal static ObjectId Empty 24 { 25 get { return new ObjectId("000000000000000000000000"); } 26 } 27 28 internal byte[] Value { get; private set; } 29 30 /// <summary> 31 /// 獲取一個新的<see cref="ObjectId"/>。 32 /// </summary> 33 /// <returns></returns> 34 public static ObjectId NewId() 35 { 36 return new ObjectId { Value = ObjectIdGenerator.Generate() }; 37 } 38 39 internal static bool TryParse(string value, out ObjectId objectId) 40 { 41 objectId = Empty; 42 if (value == null || value.Length != 24) 43 { 44 return false; 45 } 46 47 try 48 { 49 objectId = new ObjectId(value); 50 return true; 51 } 52 catch (FormatException) 53 { 54 return false; 55 } 56 } 57 58 static byte[] DecodeHex(string value) 59 { 60 if (string.IsNullOrEmpty(value)) 61 throw new ArgumentNullException("value"); 62 63 var chars = value.ToCharArray(); 64 var numberChars = chars.Length; 65 var bytes = new byte[numberChars / 2]; 66 67 for (var i = 0; i < numberChars; i += 2) 68 { 69 bytes[i / 2] = Convert.ToByte(new string(chars, i, 2), 16); 70 } 71 72 return bytes; 73 } 74 75 /// <summary> 76 /// 77 /// </summary> 78 /// <returns></returns> 79 public override int GetHashCode() 80 { 81 return Value != null ? ToString().GetHashCode() : 0; 82 } 83 84 /// <summary> 85 /// 顯示此對象的信息，便于調試。 86 /// </summary> 87 /// <returns></returns> 88 public override string ToString() 89 { 90 if (_string == null && Value != null) 91 { 92 _string = BitConverter.ToString(Value) 93 .Replace("-", string.Empty) 94 .ToLowerInvariant(); 95 } 96 97 return _string; 98 } 99 100 /// <summary> 101 /// 102 /// </summary> 103 /// <param name="obj"></param> 104 /// <returns></returns> 105 public override bool Equals(object obj) 106 { 107 var other = obj as ObjectId; 108 return Equals(other); 109 } 110 111 /// <summary> 112 /// 113 /// </summary> 114 /// <param name="other"></param> 115 /// <returns></returns> 116 public bool Equals(ObjectId other) 117 { 118 return other != null && ToString() == other.ToString(); 119 } 120 121 //public static implicit operator string(ObjectId objectId) 122 //{ 123 // return objectId == null ? null : objectId.ToString(); 124 //} 125 126 //public static implicit operator ObjectId(string value) 127 //{ 128 // return new ObjectId(value); 129 //} 130 131 /// <summary> 132 /// 133 /// </summary> 134 /// <param name="left"></param> 135 /// <param name="right"></param> 136 /// <returns></returns> 137 public static bool operator ==(ObjectId left, ObjectId right) 138 { 139 if (ReferenceEquals(left, right)) 140 { 141 return true; 142 } 143 144 if (((object)left == null) || ((object)right == null)) 145 { 146 return false; 147 } 148 149 return left.Equals(right); 150 } 151 152 /// <summary> 153 /// 154 /// </summary> 155 /// <param name="left"></param> 156 /// <param name="right"></param> 157 /// <returns></returns> 158 public static bool operator !=(ObjectId left, ObjectId right) 159 { 160 return !(left == right); 161 } 162 163 #region ISerializable 成員 164 165 const string strValue = ""; 166 void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context) 167 { 168 string value = this.ToString(); 169 info.AddValue(strValue, value); 170 } 171 172 #endregion 173 174 private ObjectId(SerializationInfo info, StreamingContext context) 175 { 176 string value = info.GetString(strValue); 177 this.Value = DecodeHex(value); 178 } 179 180 181 #region IComparable<ObjectId> 成員 182 183 /// <summary> 184 /// 根據<see cref="ObjectId.ToString()"/>的值比較兩個對象。 185 /// </summary> 186 /// <param name="other"></param> 187 /// <returns></returns> 188 public int CompareTo(ObjectId other) 189 { 190 if (other == null) { return 1; } 191 192 string thisStr = this.ToString(); 193 string otherStr = other.ToString(); 194 int result = thisStr.CompareTo(otherStr); 195 196 return result; 197 } 198 199 #endregion 200 201 #region IComparable 成員 202 203 /// <summary> 204 /// 根據<see cref="ObjectId.ToString()"/>的值比較兩個對象。 205 /// </summary> 206 /// <param name="obj"></param> 207 /// <returns></returns> 208 public int CompareTo(object obj) 209 { 210 ObjectId other = obj as ObjectId; 211 return CompareTo(other); 212 } 213 214 #endregion 215 } 216 217 internal static class ObjectIdGenerator 218 { 219 private static readonly DateTime Epoch = 220 new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc); 221 private static readonly object _innerLock = new object(); 222 private static int _counter; 223 private static readonly byte[] _machineHash = GenerateHostHash(); 224 private static readonly byte[] _processId = 225 BitConverter.GetBytes(GenerateProcessId()); 226 227 internal static byte[] Generate() 228 { 229 var oid = new byte[12]; 230 var copyidx = 0; 231 232 Array.Copy(BitConverter.GetBytes(GenerateTime()), 0, oid, copyidx, 4); 233 copyidx += 4; 234 235 Array.Copy(_machineHash, 0, oid, copyidx, 3); 236 copyidx += 3; 237 238 Array.Copy(_processId, 0, oid, copyidx, 2); 239 copyidx += 2; 240 241 Array.Copy(BitConverter.GetBytes(GenerateCounter()), 0, oid, copyidx, 3); 242 243 return oid; 244 } 245 246 private static int GenerateTime() 247 { 248 var now = DateTime.UtcNow; 249 var nowtime = new DateTime(Epoch.Year, Epoch.Month, Epoch.Day, 250 now.Hour, now.Minute, now.Second, now.Millisecond); 251 var diff = nowtime - Epoch; 252 return Convert.ToInt32(Math.Floor(diff.TotalMilliseconds)); 253 } 254 255 private static byte[] GenerateHostHash() 256 { 257 using (var md5 = MD5.Create()) 258 { 259 var host = Dns.GetHostName(); 260 return md5.ComputeHash(Encoding.Default.GetBytes(host)); 261 } 262 } 263 264 private static int GenerateProcessId() 265 { 266 var process = Process.GetCurrentProcess(); 267 return process.Id; 268 } 269 270 private static int GenerateCounter() 271 { 272 lock (_innerLock) 273 { 274 return _counter++; 275 } 276 } 277 }
使用時只需通過調用ObjectId.NewId();即可獲取一個新的編號。
分頁機制
磁盤I/O操作每次都是以4KB個字節為單位進行的。所以把單文件數據庫劃分為一個個長度為4KB的頁就很有必要。這一點稍微增加了數據庫設計圖的復雜程度。由于磁盤I/O所需時間最長，所以對此進行優化是值得的。
你可以隨意新建一個TXT文件，在里面寫幾個字符，保存一下，會看到即使是大小只有1個字節內容的TXT文件，其占用空間也是4KB。
而且所有文件的"占用空間"都是4KB的整數倍。
索引機制
我從LiteDB的文檔看到，它用Skip List實現了索引機制，能夠快速定位讀寫一個對象。Skip List是以空間換時間的方式，用擴展了的單鏈表達到了紅黑樹的效率，而其代碼比紅黑樹簡單得多。要研究、實現紅黑樹會花費更多時間，所以我效仿LiteDB用Skip List做索引。
關于Skip List大家可以參考這里，有Skip List的實現代碼。（還有很多數據結構和算法的C#實現，堪稱寶貴）還有這里（http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html）的介紹也很不錯。
Skip List的結構如下圖所示。
你只需知道Skip List在外部看起來就像一個Dictionary<TKey, TValue>，它是通過Add(TKey key, TValue value);來增加元素的。每個Skip List Node都含有一個key和一個value，而且，同一列上的結點的key和value值都相同。例如，上圖的key值為50的三個Skip List Node，其key當然都是50，而其value也必須是相同的。
關于Skip List的詳細介紹可參考維基百科。
查詢語句
創建數據庫、創建表、索引和刪除表的語句都已經不需要了。
Lambda表達式可以用作查詢語句。再次感謝LiteDB，給了我很多啟發。
不利用索引的懶惰方案
解析Lambda表達式的工作量超出我的預期，暫時先用一個懶惰的方案頂替之。LiteDB提供的解析方式也有很大局限，我還要考慮一下如何做Lambda表達式的解析。
1 /// <summary> 2 /// 查找數據庫內的某些記錄。 3 /// </summary> 4 /// <typeparam name="T"></typeparam> 5 /// <param name="predicate">符合此條件的記錄會被取出。</param> 6 /// <returns></returns> 7 public IEnumerable<T> Find<T>(Expression<Func<T, bool>> predicate) where T : Table, new() 8 { 9 if (predicate == null) { throw new ArgumentNullException("predicate"); } 10 11 // 這是沒有利用索引的版本。 12 Func<T, bool> func = predicate.Compile(); 13 foreach (T item in this.FindAll<T>()) 14 { 15 if(func(item)) 16 { 17 yield return item; 18 } 19 } 20 21 // TODO: 這是利用索引的版本，尚未實現。 22 //List<T> result = new List<T>(); 23 24 //var body = predicate.Body as LambdaExpression; 25 //this.Find(result, body); 26 27 //return result; 28 } 29 /// <summary> 30 /// 查找數據庫內所有指定類型的記錄。 31 /// </summary> 32 /// <typeparam name="T">要查找的類型。</typeparam> 33 /// <returns></returns> 34 public IEnumerable<T> FindAll<T>() where T:Table, new() 35 { 36 Type type = typeof(T); 37 if (this.tableBlockDict.ContainsKey(type)) 38 { 39 TableBlock tableBlock = this.tableBlockDict[type]; 40 IndexBlock firstIndex = tableBlock.IndexBlockHead.NextObj;// 第一個索引應該是Table.Id的索引。 41 FileStream fs = this.fileStream; 42 43 SkipListNodeBlock current = firstIndex.SkipListHeadNodes[0]; //currentHeadNode; 44 45 while (current.RightPos != firstIndex.SkipListTailNodePos) 46 { 47 current.TryLoadProperties(fs, SkipListNodeBlockLoadOptions.RightObj); 48 current.RightObj.TryLoadProperties(fs, SkipListNodeBlockLoadOptions.RightObj | SkipListNodeBlockLoadOptions.Value); 49 T item = current.RightObj.Value.GetObject<T>(this); 50 51 yield return item; 52 53 current = current.RightObj; 54 } 55 } 56 }
Lambda表達式
在MSDN上有關于Lambda表達式的介紹。
System.Object
System.Linq.Expressions.Expression
System.Linq.Expressions.BinaryExpression
System.Linq.Expressions.BlockExpression
System.Linq.Expressions.ConditionalExpression
System.Linq.Expressions.ConstantExpression
System.Linq.Expressions.DebugInfoExpression
System.Linq.Expressions.DefaultExpression
System.Linq.Expressions.DynamicExpression
System.Linq.Expressions.GotoExpression
System.Linq.Expressions.IndexExpression
System.Linq.Expressions.InvocationExpression
System.Linq.Expressions.LabelExpression
System.Linq.Expressions.LambdaExpression
System.Linq.Expressions.ListInitExpression
System.Linq.Expressions.LoopExpression
System.Linq.Expressions.MemberExpression
System.Linq.Expressions.MemberInitExpression
System.Linq.Expressions.MethodCallExpression
System.Linq.Expressions.NewArrayExpression
System.Linq.Expressions.NewExpression
System.Linq.Expressions.ParameterExpression
System.Linq.Expressions.RuntimeVariablesExpression
System.Linq.Expressions.SwitchExpression
System.Linq.Expressions.TryExpression
System.Linq.Expressions.TypeBinaryExpression
System.Linq.Expressions.UnaryExpression
這個列表放在這里是為了方便了解lambda表達式都有哪些類型的結點。我還整理了描述表達式目錄樹的節點的節點類型System.Linq.Expressions. ExpressionType。
1 namespace System.Linq.Expressions 2 { 3 /// <summary> 4 /// 描述表達式目錄樹的節點的節點類型。 5 /// </summary> 6 public enum ExpressionType 7 { 8 /// <summary> 9 /// 加法運算，如 a + b，針對數值操作數，不進行溢出檢查。 10 /// </summary> 11 Add = 0, 12 // 13 /// <summary> 14 /// 加法運算，如 (a + b)，針對數值操作數，進行溢出檢查。 15 /// </summary> 16 AddChecked = 1, 17 // 18 /// <summary> 19 /// 按位或邏輯 AND 運算，如 C# 中的 (a & b) 和 Visual Basic 中的 (a And b)。 20 /// </summary> 21 And = 2, 22 // 23 /// <summary> 24 /// 條件 AND 運算，它僅在第一個操作數的計算結果為 true 時才計算第二個操作數。 它與 C# 中的 (a && b) 和 Visual Basic 中的 (a AndAlso b) 對應。 25 /// </summary> 26 AndAlso = 3, 27 // 28 /// <summary> 29 /// 獲取一維數組長度的運算，如 array.Length。 30 /// </summary> 31 ArrayLength = 4, 32 // 33 /// <summary> 34 /// 一維數組中的索引運算，如 C# 中的 array[index] 或 Visual Basic 中的 array(index)。 35 /// </summary> 36 ArrayIndex = 5, 37 // 38 /// <summary> 39 /// 方法調用，如在 obj.sampleMethod() 表達式中。 40 /// </summary> 41 Call = 6, 42 // 43 /// <summary> 44 /// 表示 null 合并運算的節點，如 C# 中的 (a ?? b) 或 Visual Basic 中的 If(a, b)。 45 /// </summary> 46 Coalesce = 7, 47 // 48 /// <summary> 49 /// 條件運算，如 C# 中的 a > b ? a : b 或 Visual Basic 中的 If(a > b, a, b)。 50 /// </summary> 51 Conditional = 8, 52 // 53 /// <summary> 54 /// 一個常量值。 55 /// </summary> 56 Constant = 9, 57 // 58 /// <summary> 59 /// 強制轉換或轉換運算，如 C#中的 (SampleType)obj 或 Visual Basic 中的 CType(obj, SampleType)。 60 /// 對于數值轉換，如果轉換后的值對于目標類型來說太大，這不會引發異常。 61 /// </summary> 62 Convert = 10, 63 // 64 /// <summary> 65 /// 強制轉換或轉換運算，如 C#中的 (SampleType)obj 或 Visual Basic 中的 CType(obj, SampleType)。 66 /// 對于數值轉換，如果轉換后的值與目標類型大小不符，則引發異常。 67 /// </summary> 68 ConvertChecked = 11, 69 // 70 /// <summary> 71 /// 除法運算，如 (a / b)，針對數值操作數。 72 /// </summary> 73 Divide = 12, 74 // 75 /// <summary> 76 /// 表示相等比較的節點，如 C# 中的 (a == b) 或 Visual Basic 中的 (a = b)。 77 /// </summary> 78 Equal = 13, 79 // 80 /// <summary> 81 /// 按位或邏輯 XOR 運算，如 C# 中的 (a ^ b) 或 Visual Basic 中的 (a Xor b)。 82 /// </summary> 83 ExclusiveOr = 14, 84 // 85 /// <summary> 86 /// “大于”比較，如 (a > b)。 87 /// </summary> 88 GreaterThan = 15, 89 // 90 /// <summary> 91 /// “大于或等于”比較，如 (a >= b)。 92 /// </summary> 93 GreaterThanOrEqual = 16, 94 // 95 /// <summary> 96 /// 調用委托或 lambda 表達式的運算，如 sampleDelegate.Invoke()。 97 /// </summary> 98 Invoke = 17, 99 // 100 /// <summary> 101 /// lambda 表達式，如 C# 中的 a => a + a 或 Visual Basic 中的 Function(a) a + a。 102 /// </summary> 103 Lambda = 18, 104 // 105 /// <summary> 106 /// 按位左移運算，如 (a << b)。 107 /// </summary> 108 LeftShift = 19, 109 // 110 /// <summary> 111 /// “小于”比較，如 (a < b)。 112 /// </summary> 113 LessThan = 20, 114 // 115 /// <summary> 116 /// “小于或等于”比較，如 (a <= b)。 117 /// </summary> 118 LessThanOrEqual = 21, 119 // 120 /// <summary> 121 /// 創建新的 System.Collections.IEnumerable 對象并從元素列表中初始化該對象的運算，如 C# 中的 new List<SampleType>(){ 122 /// a, b, c } 或 Visual Basic 中的 Dim sampleList = { a, b, c }。 123 /// </summary> 124 ListInit = 22, 125 // 126 /// <summary> 127 /// 從字段或屬性進行讀取的運算，如 obj.SampleProperty。 128 /// </summary> 129 MemberAccess = 23, 130 // 131 /// <summary> 132 /// 創建新的對象并初始化其一個或多個成員的運算，如 C# 中的 new Point { X = 1, Y = 2 } 或 Visual Basic 中的 133 /// New Point With {.X = 1, .Y = 2}。 134 /// </summary> 135 MemberInit = 24, 136 // 137 /// <summary> 138 /// 算術余數運算，如 C# 中的 (a % b) 或 Visual Basic 中的 (a Mod b)。 139 /// </summary> 140 Modulo = 25, 141 // 142 /// <summary> 143 /// 乘法運算，如 (a * b)，針對數值操作數，不進行溢出檢查。 144 /// </summary> 145 Multiply = 26, 146 // 147 /// <summary> 148 /// 乘法運算，如 (a * b)，針對數值操作數，進行溢出檢查。 149 /// </summary> 150 MultiplyChecked = 27, 151 // 152 /// <summary> 153 /// 算術求反運算，如 (-a)。 不應就地修改 a 對象。 154 /// </summary> 155 Negate = 28, 156 // 157 /// <summary> 158 /// 一元加法運算，如 (+a)。 預定義的一元加法運算的結果是操作數的值，但用戶定義的實現可以產生特殊結果。 159 /// </summary> 160 UnaryPlus = 29, 161 // 162 /// <summary> 163 /// 算術求反運算，如 (-a)，進行溢出檢查。 不應就地修改 a 對象。 164 /// </summary> 165 NegateChecked = 30, 166 // 167 /// <summary> 168 /// 調用構造函數創建新對象的運算，如 new SampleType()。 169 /// </summary> 170 New = 31, 171 // 172 /// <summary> 173 /// 創建新的一維數組并從元素列表中初始化該數組的運算，如 C# 中的 new SampleType[]{a, b, c} 或 Visual Basic 174 /// 中的 New SampleType(){a, b, c}。 175 /// </summary> 176 NewArrayInit = 32, 177 // 178 /// <summary> 179 /// 創建新數組（其中每個維度的界限均已指定）的運算，如 C# 中的 new SampleType[dim1, dim2] 或 Visual Basic 180 /// 中的 New SampleType(dim1, dim2)。 181 /// </summary> 182 NewArrayBounds = 33, 183 // 184 /// <summary> 185 /// 按位求補運算或邏輯求反運算。 在 C# 中，它與整型的 (~a) 和布爾值的 (!a) 等效。 在 Visual Basic 中，它與 (Not 186 /// a) 等效。 不應就地修改 a 對象。 187 /// </summary> 188 Not = 34, 189 // 190 /// <summary> 191 /// 不相等比較，如 C# 中的 (a != b) 或 Visual Basic 中的 (a <> b)。 192 /// </summary> 193 NotEqual = 35, 194 // 195 /// <summary> 196 /// 按位或邏輯 OR 運算，如 C# 中的 (a | b) 或 Visual Basic 中的 (a Or b)。 197 /// </summary> 198 Or = 36, 199 // 200 /// <summary> 201 /// 短路條件 OR 運算，如 C# 中的 (a || b) 或 Visual Basic 中的 (a OrElse b)。 202 /// </summary> 203 OrElse = 37, 204 // 205 /// <summary> 206 /// 對在表達式上下文中定義的參數或變量的引用。 有關更多信息，請參見 System.Linq.Expressions.ParameterExpression。 207 /// </summary> 208 Parameter = 38, 209 // 210 /// <summary> 211 /// 對某個數字進行冪運算的數學運算，如 Visual Basic 中的 (a ^ b)。 212 /// </summary> 213 Power = 39, 214 // 215 /// <summary> 216 /// 具有類型為 System.Linq.Expressions.Expression 的常量值的表達式。 System.Linq.Expressions.ExpressionType.Quote 217 /// 節點可包含對參數的引用，這些參數在該節點表示的表達式的上下文中定義。 218 /// </summary> 219 Quote = 40, 220 // 221 /// <summary> 222 /// 按位右移運算，如 (a >> b)。 223 /// </summary> 224 RightShift = 41, 225 // 226 /// <summary> 227 /// 減法運算，如 (a - b)，針對數值操作數，不進行溢出檢查。 228 /// </summary> 229 Subtract = 42, 230 // 231 /// <summary> 232 /// 算術減法運算，如 (a - b)，針對數值操作數，進行溢出檢查。 233 /// </summary> 234 SubtractChecked = 43, 235 // 236 /// <summary> 237 /// 顯式引用或裝箱轉換，其中如果轉換失敗則提供 null，如 C# 中的 (obj as SampleType) 或 Visual Basic 中的 238 /// TryCast(obj, SampleType)。 239 /// </summary> 240 TypeAs = 44, 241 // 242 /// <summary> 243 /// 類型測試，如 C# 中的 obj is SampleType 或 Visual Basic 中的 TypeOf obj is SampleType。 244 /// </summary> 245 TypeIs = 45, 246 // 247 /// <summary> 248 /// 賦值運算，如 (a = b)。 249 /// </summary> 250 Assign = 46, 251 // 252 /// <summary> 253 /// 表達式塊。 254 /// </summary> 255 Block = 47, 256 // 257 /// <summary> 258 /// 調試信息。 259 /// </summary> 260 DebugInfo = 48, 261 // 262 /// <summary> 263 /// 一元遞減運算，如 C# 和 Visual Basic 中的 (a - 1)。 不應就地修改 a 對象。 264 /// </summary> 265 Decrement = 49, 266 // 267 /// <summary> 268 /// 動態操作。 269 /// </summary> 270 Dynamic = 50, 271 // 272 /// <summary> 273 /// 默認值。 274 /// </summary> 275 Default = 51, 276 // 277 /// <summary> 278 /// 擴展表達式。 279 /// </summary> 280 Extension = 52, 281 // 282 /// <summary> 283 /// “跳轉”表達式，如 C# 中的 goto Label 或 Visual Basic 中的 GoTo Label。 284 /// </summary> 285 Goto = 53, 286 // 287 /// <summary> 288 /// 一元遞增運算，如 C# 和 Visual Basic 中的 (a + 1)。 不應就地修改 a 對象。 289 /// </summary> 290 Increment = 54, 291 // 292 /// <summary> 293 /// 索引運算或訪問使用參數的屬性的運算。 294 /// </summary> 295 Index = 55, 296 // 297 /// <summary> 298 /// 標簽。 299 /// </summary> 300 Label = 56, 301 // 302 /// <summary> 303 /// 運行時變量的列表。 有關更多信息，請參見 System.Linq.Expressions.RuntimeVariablesExpression。 304 /// </summary> 305 RuntimeVariables = 57, 306 // 307 /// <summary> 308 /// 循環，如 for 或 while。 309 /// </summary> 310 Loop = 58, 311 // 312 /// <summary> 313 /// 多分支選擇運算，如 C# 中的 switch 或 Visual Basic 中的 Select Case。 314 /// </summary> 315 Switch = 59, 316 // 317 /// <summary> 318 /// 引發異常的運算，如 throw new Exception()。 319 /// </summary> 320 Throw = 60, 321 // 322 /// <summary> 323 /// try-catch 表達式。 324 /// </summary> 325 Try = 61, 326 // 327 /// <summary> 328 /// 取消裝箱值類型運算，如 MSIL 中的 unbox 和 unbox.any 指令。 329 /// </summary> 330 Unbox = 62, 331 // 332 /// <summary> 333 /// 加法復合賦值運算，如 (a += b)，針對數值操作數，不進行溢出檢查。 334 /// </summary> 335 AddAssign = 63, 336 // 337 /// <summary> 338 /// 按位或邏輯 AND 復合賦值運算，如 C# 中的 (a &= b)。 339 /// </summary> 340 AndAssign = 64, 341 // 342 /// <summary> 343 /// 除法復合賦值運算，如 (a /= b)，針對數值操作數。 344 /// </summary> 345 DivideAssign = 65, 346 // 347 /// <summary> 348 /// 按位或邏輯 XOR 復合賦值運算，如 C# 中的 (a ^= b)。 349 /// </summary> 350 ExclusiveOrAssign = 66, 351 // 352 /// <summary> 353 /// 按位左移復合賦值運算，如 (a <<= b)。 354 /// </summary> 355 LeftShiftAssign = 67, 356 // 357 /// <summary> 358 /// 算術余數復合賦值運算，如 C# 中的 (a %= b)。 359 /// </summary> 360 ModuloAssign = 68, 361 // 362 /// <summary> 363 /// 乘法復合賦值運算，如 (a *= b)，針對數值操作數，不進行溢出檢查。 364 /// </summary> 365 MultiplyAssign = 69, 366 // 367 /// <summary> 368 /// 按位或邏輯 OR 復合賦值運算，如 C# 中的 (a |= b)。 369 /// </summary> 370 OrAssign = 70, 371 // 372 /// <summary> 373 /// 對某個數字進行冪運算的復合賦值運算，如 Visual Basic 中的 (a ^= b)。 374 /// </summary> 375 PowerAssign = 71, 376 // 377 /// <summary> 378 /// 按位右移復合賦值運算，如 (a >>= b)。 379 /// </summary> 380 RightShiftAssign = 72, 381 // 382 /// <summary> 383 /// 減法復合賦值運算，如 (a -= b)，針對數值操作數，不進行溢出檢查。 384 /// </summary> 385 SubtractAssign = 73, 386 // 387 /// <summary> 388 /// 加法復合賦值運算，如 (a += b)，針對數值操作數，進行溢出檢查。 389 /// </summary> 390 AddAssignChecked = 74, 391 // 392 /// <summary> 393 /// 乘法復合賦值運算，如 (a *= b)，針對數值操作數，進行溢出檢查。 394 /// </summary> 395 MultiplyAssignChecked = 75, 396 // 397 /// <summary> 398 /// 減法復合賦值運算，如 (a -= b)，針對數值操作數，進行溢出檢查。 399 /// </summary> 400 SubtractAssignChecked = 76, 401 // 402 /// <summary> 403 /// 一元前綴遞增，如 (++a)。 應就地修改 a 對象。 404 /// </summary> 405 PreIncrementAssign = 77, 406 // 407 /// <summary> 408 /// 一元前綴遞減，如 (--a)。 應就地修改 a 對象。 409 /// </summary> 410 PreDecrementAssign = 78, 411 // 412 /// <summary> 413 /// 一元后綴遞增，如 (a++)。 應就地修改 a 對象。 414 /// </summary> 415 PostIncrementAssign = 79, 416 // 417 /// <summary> 418 /// 一元后綴遞減，如 (a--)。 應就地修改 a 對象。 419 /// </summary> 420 PostDecrementAssign = 80, 421 // 422 /// <summary> 423 /// 確切類型測試。 424 /// </summary> 425 TypeEqual = 81, 426 // 427 /// <summary> 428 /// 二進制反碼運算，如 C# 中的 (~a)。 429 /// </summary> 430 OnesComplement = 82, 431 // 432 /// <summary> 433 /// true 條件值。 434 /// </summary> 435 IsTrue = 83, 436 // 437 /// <summary> 438 /// false 條件值。 439 /// </summary> 440 IsFalse = 84, 441 } 442 }
在查詢條件方面，要做的就是解析其中一些類型的表達式。
常用表達式舉例
下面列舉出常用的查詢語句。
1 System.Linq.Expressions.Expression<Func<Cat, bool>> pre = null; 2 3 pre = x => x.Price == 10; 4 pre = x => x.Price < 10; 5 pre = x => x.Price > 10; 6 pre = x => x.Price < 10 || x.Price > 20; 7 pre = x => 10 < x.Price && x.Price < 20; 8 pre = x => x.KittyName.Contains("2"); 9 pre = x => x.KittyName.StartsWith("kitty"); 10 pre = x => x.KittyName.EndsWith("2");
數據庫文件的邏輯結構
塊(Block)
數據庫文件中要保存所有的表(Table)信息、各個表(Table)的索引(Index)信息、各個索引下的Skip List結點(Skip List Node)信息、各個Skip List Node的key和value（這是所有的數據庫記錄對象所在的位置）信息和所有的數據庫記錄。我們為不同種類的的信息分別設計一個類型，稱為XXXBlock，它們都繼承抽象類型Block。我們還規定，不同類型的Block只能存放在相應類型的頁里（只有一個例外）。這樣似乎效率更高。
文件鏈表
一個數據庫，會有多個表(Table)。數據庫里的表的數量隨時會增加減少。要想把多個表存儲到文件里，以后還能全部讀出來，最好使用鏈表結構。我們用TableBlock描述存儲到數據庫文件里的一個表(Table)。TableBlock是在文件中的一個鏈表結點，其NextPos是指向文件中的某個位置的指針。只要有NextPos，就可以反序列化出NextObj，也就是下一個TableBlock。我把這種在文件中存在的鏈表稱為文件鏈表。以前所見所用的鏈表則是內存鏈表。
一個表里，會有多個索引(Index)，類似的，IndexBlock也是一個文件鏈表。
SkipListNodeBlock存儲的是Skip List的一個結點，而Skip List的結點有Down和Right兩個指針，所以SkipListNodeBlock要存儲兩個指向文件中某處位置的指針DownPos和RightPos。就是說，SkipListNodeBlock是一個擴展了的文件鏈表。
了解了這些概念，就可以繼續設計了。
Block
任何一個塊，都必須知道自己應該存放到數據庫文件的位置(ThisPos)。為了能夠進行序列化和反序列化，都要有[Serializable]特性。為了控制序列化和反序列化過程，要實現ISerializable接口。
1 /// <summary> 2 /// 存儲到數據庫文件的一塊內容。 3 /// </summary> 4 [Serializable] 5 public abstract class Block : ISerializable 6 { 7 8 #if DEBUG 9 10 /// <summary> 11 /// 創建新<see cref="Block"/>時應設置其<see cref="Block.blockID"/>為計數器，并增長此計數器值。 12 /// </summary> 13 internal static long IDCounter = 0; 14 15 /// <summary> 16 /// 用于給此塊標記一個編號，僅為便于調試之用。 17 /// </summary> 18 public long blockID; 19 #endif 20 21 /// <summary> 22 /// 此對象自身在數據庫文件中的位置。為0時說明尚未指定位置。只有<see cref="DBHeaderBlock"/>的位置才應該為0。 23 /// <para>請注意在讀寫時設定此值。</para> 24 /// </summary> 25 public long ThisPos { get; set; } 26 27 /// <summary> 28 /// 存儲到數據庫文件的一塊內容。 29 /// </summary> 30 public Block() 31 { 32 #if DEBUG 33 this.blockID = IDCounter++; 34 #endif 35 BlockCache.AddFloatingBlock(this); 36 } 37 38 #if DEBUG 39 const string strBlockID = ""; 40 #endif 41 42 #region ISerializable 成員 43 44 /// <summary> 45 /// 序列化時系統會調用此方法。 46 /// </summary> 47 /// <param name="info"></param> 48 /// <param name="context"></param> 49 public virtual void GetObjectData(SerializationInfo info, StreamingContext context) 50 { 51 #if DEBUG 52 info.AddValue(strBlockID, this.blockID); 53 #endif 54 } 55 56 #endregion 57 58 /// <summary> 59 /// BinaryFormatter會通過調用此方法來反序列化此塊。 60 /// </summary> 61 /// <param name="info"></param> 62 /// <param name="context"></param> 63 protected Block(SerializationInfo info, StreamingContext context) 64 { 65 #if DEBUG 66 this.blockID = info.GetInt64(strBlockID); 67 #endif 68 } 69 70 /// <summary> 71 /// 顯示此塊的信息，便于調試。 72 /// </summary> 73 /// <returns></returns> 74 public override string ToString() 75 { 76 #if DEBUG 77 return string.Format("{0}: ID:{1}, Pos: {2}", this.GetType().Name, this.blockID, this.ThisPos); 78 #else 79 return string.Format("{0}: Pos: {1}", this.GetType().Name, this.ThisPos); 80 #endif 81 } 82 83 /// <summary> 84 /// 安排所有文件指針。如果全部安排完畢，返回true，否則返回false。 85 /// </summary> 86 /// <returns></returns> 87 public abstract bool ArrangePos(); 88 }
DBHeaderBlock
這是整個數據庫的頭部，用于保存在數據庫范圍內的全局變量。它在整個數據庫中只有一個，并且放在數據庫的第一頁（0~4095字節里）。
TableBlock
TableBlock存放某種類型的表(Table)的信息，包括索引的頭結點位置和下一個TableBlock的位置。前面說過，TableBlock是內存鏈表的一個結點。鏈表最好有個頭結點，頭結點不存儲具有業務價值的數據，但是它會為編碼提供方便。考慮到數據庫的第一頁只存放著一個DBHeaderBlock，我們就把TableBlock的頭結點緊挨著放到DBHeaderBlock后面。這就是上面所說的唯一的例外。由于TableBlock的頭結點不會移動位置，其序列化后的字節數也不會變，所以放這里是沒有問題的。
IndexBlock
IndexBlock存儲Table的一個索引。IndexBlock也是內存鏈表的一個結點。而它內部含有指向SkipListNodeBlock的指針，所以，實際上IndexBlock就充當了SkipList。
SkipListNodeBlock
如前所述，這是一個擴展了的文件鏈表的結點。此結點的key和value都是指向實際數據的文件指針。如果直接保存實際數據，那么每個結點都保存一份完整的數據會造成很大的浪費。特別是value，如果value里有一個序列化了的圖片，那是不可想象的。而且這樣一來，所有的SkipListNodeBlock序列化的長度都是相同的。
DataBlock
DataBlock也是文件鏈表的一個結點。由于某些數據庫記錄會很大（比如要存儲一個System.Drawing.Image），一個頁只有4KB，無法放下。所以可能需要把一條記錄劃分為多個數據塊，放到多個DataBlock里。也就是說，一個數據庫記錄是用一個鏈表保存的。
PageHeaderBlock
為了以后管理頁（申請新頁、釋放不再使用的頁、申請一定長度的空閑空間），我們在每個頁的起始位置都放置一個PageHeaderBlock，用來保存此頁的狀態（可用字節數等）。并且，每個頁都包含一個指向下一相同類型的頁的位置的文件指針。這樣，所有存放TableBlock的頁就成為一個文件鏈表，所有存放IndexBlock的頁就成為另一個文件鏈表，所有存放SkipListNodeBlock的頁也成為一個文件鏈表，所有存放DataBlock的頁也一樣。
另外，在刪除某些記錄后，有的頁里存放的塊可能為0，這時就成為一個空白頁(Empty Page)，所以我們還要把這些空白頁串聯成一個文件鏈表。
總之，文件里的鏈表關系無處不在。
塊(Block)在數據庫文件里
下面是我畫的一個數據庫文件的邏輯上的結構圖。它展示了各種類型的塊在數據庫文件里的生存狀態。
首先，剛剛創建一個數據庫文件時，文件里是這樣的：
當前只有一個DBHeaderBlock和一個TableBlock（作為頭結點）。
注意：此時我們忽略"頁"這個概念，所以在每個頁最開始處的PageHeaderBlock就不考慮了。
之后我們Insert一條記錄，這會在數據庫里新建一個表及其索引信息，然后插入此記錄。指向完畢后，數據庫文件里就是這樣的。
之前的TableBlock頭結點指向了新建的TableBlock的位置，新建的TableBlock創建了自己的索引。
索引有兩個結點，上面的那個是索引的頭結點，其不包含有業務價值的信息，只指向下一個索引結點。
下一個索引結點是第一個有業務意義的索引結點，也是一個存在于文件中的SkipList，它有自己的一群SkipListNodeBlock。在插入第一條記錄前，這群SkipListNodeBlock只有豎直方向的那5個（實際上我在數據庫文件里設定的是32個，不過沒法畫那么多，就用5個指代了）。
現在表和索引創建完畢，開始插入第一條記錄。這會隨機創建若干個（這里是2個）SkipListNodeBlock（這是Skip List數據結構的特性，具體請參考維基百科。這兩個SkipListNodeBlock的keyPos和valuePos都指向了key和value所在的DataBlock的位置。用于存儲value的DataBlock有2個結點，說明value（數據庫記錄序列化后的字節數）比較大，一個頁占不下。
這就是我們期望的情況。為了實現這種文件鏈表，還需要后續一些遍歷操作。我們將結合事務來完成它。
如果你感興趣，下面是繼續插入第二條記錄后的情況：
注：為了避免圖紙太亂，我只畫出了最下面的K1, V1和K2, V2的指針指向DataBlock。實際上，各個K1, V1和K2, V2都是指向DataBlock的。
為塊(Block)安排其在文件中的位置
根據依賴關系依次分配
新創建一個Block時，其在數據庫文件中的位置(Block.ThisPos)都沒有指定，那么在其它Block中指向它的那些字段/屬性值就無法確定。我們通過兩個步驟來解決此問題。
首先，我們給每個文件鏈表結點的NextPos都配備一個對應的NextObj。就是說，新創建的Block雖然在文件鏈表方面還沒有安排好指針，但是在內存鏈表方面已經安排好了。
然后，等所需的所有Block都創建完畢，遍歷這些Block，那些在內存鏈表中處于最后一個的結點，其字段/屬性值不依賴其它Block的位置，因此可以直接為其分配好在文件里的位置和空間。之后再次遍歷這些Block，那些依賴最后一個結點的結點，此時也就可以為其設置字段/屬性值了。以此類推，多次遍歷，直到所有Block的字段/屬性值都設置完畢。
1 // 給所有的塊安排數據庫文件中的位置。 2 List<Block> arrangedBlocks = new List<Block>(); 3 while (arrangedBlocks.Count < this.blockList.Count) 4 { 5 for (int i = this.blockList.Count - 1; i >= 0; i--)// 后加入列表的先處理。 6 { 7 Block block = this.blockList[i]; 8 if (arrangedBlocks.Contains(block)) { continue; } 9 bool done = block.ArrangePos(); 10 if (done) 11 { 12 if (block.ThisPos == 0) 13 { 14 byte[] bytes = block.ToBytes(); 15 if (bytes.Length > Consts.maxAvailableSpaceInPage) 16 { throw new Exception("Block size is toooo large!"); } 17 AllocPageTypes pageType = block.BelongedPageType(); 18 AllocatedSpace space = this.fileDBContext.Alloc(bytes.LongLength, pageType); 19 block.ThisPos = space.position; 20 } 21 22 arrangedBlocks.Add(block); 23 } 24 } 25 }
我們要為不同類型的塊執行各自的字段/屬性值的設置方法，通過繼承Block基類的abstract bool ArrangePos();來實現。實際上，只要添加到blockList里的順序得當，只需一次遍歷即可完成所有的自動/屬性值的設置。
DBHeaderBlock
此類型的字段/屬性值不依賴其它任何Block，永遠都是實時分配完成的。
1 internal override bool ArrangePos() 2 { 3 return true;// 此類型比較特殊，應該在更新時立即指定各項文件指針。 4 }
TableBlock
作為頭結點的那個TableBlock不含索引，因此其字段/屬性值不需設置。其它TableBlock則需要保存索引頭結點的位置。
作為鏈表的最后一個結點的那個TableBlock的字段/屬性值不依賴其它TableBlock的位置，其它TableBLock則需要其下一個TableBlock的位置。這一規則對每個文件鏈表都適用。
1 public override bool ArrangePos() 2 { 3 bool allArranged = true; 4 5 if (this.IndexBlockHead != null)// 如果IndexBlockHead == null，則說明此塊為TableBlock的頭結點。頭結點是不需要持有索引塊的。 6 { 7 if (this.IndexBlockHead.ThisPos != 0) 8 { this.IndexBlockHeadPos = this.IndexBlockHead.ThisPos; } 9 else 10 { allArranged = false; } 11 } 12 13 if (this.NextObj != null) 14 { 15 if (this.NextObj.ThisPos != 0) 16 { this.NextPos = this.NextObj.ThisPos; } 17 else 18 { allArranged = false; } 19 } 20 21 return allArranged; 22 }
IndexBlock
IndexBlock也是文件鏈表的一個結點，其字段/屬性值的設置方式與TableBlock相似。
1 public override bool ArrangePos() 2 { 3 bool allArranged = true; 4 5 if (this.SkipListHeadNodes != null)// 如果這里的SkipListHeadNodes == null，則說明此索引塊是索引鏈表里的頭結點。頭結點是不需要SkipListHeadNodes有數據的。 6 { 7 int length = this.SkipListHeadNodes.Length; 8 if (length == 0) 9 { throw new Exception("SKip List's head nodes has 0 element!"); } 10 long pos = this.SkipListHeadNodes[length - 1].ThisPos; 11 if (pos != 0) 12 { this.SkipListHeadNodePos = pos; } 13 else 14 { allArranged = false; } 15 } 16 17 if (this.SkipListTailNode != null)// 如果這里的SkipListTailNodes == null，則說明此索引塊是索引鏈表里的頭結點。頭結點是不需要SkipListTailNodes有數據的。 18 { 19 long pos = this.SkipListTailNode.ThisPos; 20 if (pos != 0) 21 { this.SkipListTailNodePos = pos; } 22 else 23 { allArranged = false; } 24 } 25 26 if (this.NextObj != null) 27 { 28 if (this.NextObj.ThisPos != 0) 29 { this.NextPos = this.NextObj.ThisPos; } 30 else 31 { allArranged = false; } 32 } 33 34 return allArranged; 35 }
SkipListNodeBlock
SkipListNodeBlock是擴展了的文件鏈表，關于指向下一結點的指針的處理與前面類似。作為頭結點的SkipListNodeBlock的Key和Value都是null，是不依賴其它Block的。非頭結點的SkipListNodeBlock的Key和Value則依賴保存著序列化后的Key和Value的DataBlock。
1 public override bool ArrangePos() 2 { 3 bool allArranged = true; 4 5 if (this.Key != null) 6 { 7 if (this.Key.ThisPos != 0) 8 { this.KeyPos = this.Key.ThisPos; } 9 else 10 { allArranged = false; } 11 } 12 13 if (this.Value != null) 14 { 15 if (this.Value[0].ThisPos != 0) 16 { this.ValuePos = this.Value[0].ThisPos; } 17 else 18 { allArranged = false; } 19 } 20 21 if (this.DownObj != null)// 此結點不是最下方的結點。 22 { 23 if (this.DownObj.ThisPos != 0) 24 { this.DownPos = this.DownObj.ThisPos; } 25 else 26 { allArranged = false; } 27 } 28 29 if (this.RightObj != null)// 此結點不是最右方的結點。 30 { 31 if (this.RightObj.ThisPos != 0) 32 { this.RightPos = this.RightObj.ThisPos; } 33 else 34 { allArranged = false; } 35 } 36 37 return allArranged; 38 }
DataBlock
DataBlock就是一個很單純的文件鏈表結點。
1 public override bool ArrangePos() 2 { 3 bool allArranged = true; 4 5 if (NextObj != null) 6 { 7 if (NextObj.ThisPos != 0) 8 { this.NextPos = NextObj.ThisPos; } 9 else 10 { allArranged = false; } 11 } 12 13 return allArranged; 14 }
PageHeaderBlock
此類型只在創建新頁和申請已有頁空間時出現，不會參與上面各類Block的位置分配，而是在創建時就為其安排好NextPagePos等屬性。
1 internal override bool ArrangePos() 2 { 3 return true;// 此類型比較特殊，應該在創建時就為其安排好NextPagePos等屬性。 4 }
Demo和工具
為了方便調試和使用SharpFileDB，我做了下面這些工具和示例Demo。
Demo：MyNote
這是一個非常簡單的Demo，實現一個簡單的便簽列表，演示了如何使用SharpFileDB。雖然界面不好看，但是用作Demo也不應該有太多的無關代碼。
查看數據庫狀態
為了能夠直觀地查看數據庫的狀態（包含哪些表、索引、數據記錄），方便調試，這里順便提供一個Winform程序"SharpFileDB Viewer"。這樣可以看到數據庫的幾乎全部信息，調試起來就方便多了。
點擊"Refresh"會重新加載所有的表、索引和記錄信息，簡單粗暴。
點擊"Skip Lists"會把數據庫里所有表的所有索引的所有結點和所有數據都畫到BMP圖片上。比如上面看到的MyNote.db的索引分別情況如下圖所示。
此圖繪制了Note表的唯一一個索引和表里的全部記錄（共10條）。
由于為Skip List指定了最大層數為8，且現在數據庫里只有10條記錄，所以圖示上方比較空曠。
下面是局部視圖，看得比較清楚。
點擊"Blocks"會把數據庫各個頁上包含的各個塊的占用情況畫到多個寬為4096高為100的BMP圖片上。例如下面6張圖是添加了一個表、一個索引和一條記錄后，數據庫文件的全部6個頁的情況。
如上圖所示，每一頁頭部都含有一個PageHeaderBlock，用淺綠色表示。
第一頁還有一個數據庫頭部DBHeaderBlock（用青紫色表示）和一個TableBlock頭結點（用橙色表示）。第六頁也有一個TableBlock，它代表目前數據庫的唯一一個表。Table頭結點的TableType屬性是空的，所以其長度比第六頁的TableBlock要短。這些圖片是完全準確地依照各個Block在數據庫文件中存儲的位置和長度繪制的。
第二頁是2個DataBlock，用金色表示。（DataBlock里存放的才是有業務價值的數據，所以是金子的顏色）
第三、第四頁存放的都是SkipListNodeBlock（用綠色表示）。可見索引是比較占地方的。
第五頁存放了兩個IndexBlock（其中一個是IndexBlock的頭結點），用灰色表示。
這些圖片就比前面手工畫的草圖好看多了。
以后有時間我把這些圖片畫到Form上，當鼠標停留在一個塊上時，會顯示此塊的具體信息（如位置、長度、類型、相關聯的塊等），那就更方便監視數據庫的狀態了。
后續我會根據需要增加顯示更多信息的功能。
可視化的數據庫設計器
如果能像MSSQLServer那樣用可視化的方法創建自定義表，做成自己的數據庫，那就最好了。所以我寫了這樣一個可視化的數據庫設計器，你可以用可視化方式設計你的數據庫，然后一鍵生成所有代碼。
規則/坑
各種各樣的庫、工具包都有一些隱晦的規則，一旦觸及就會引發各種奇怪的問題。這種規則其實就是坑。SharpFileDB盡可能不設坑或不設深坑。那些實在無法阻擋的坑，我就讓它淺淺地、明顯地存在著，即使掉進去了也能馬上跳出來。另外，通過使用可視化的設計器，還可以自動避免掉坑里，因為設計器在生成代碼前是會提醒你是否已經一腳進坑了。
SharpFileDB有如下幾條規則（幾個坑）你需要知道：
繼承Table的表類型序列化后不能太大
你設計的Table類型序列化后的長度不能超過Int32.MaxValue個字節（= 2097151KB = 2047MB ≈2GB）。這個坑夠淺了吧。如果一個對象能占據2GB，那早就不該用SharpFileDB了。所以這個坑應該不會有人踩到。
只能在屬性上添加索引
索引必須加在屬性上，否則無效。為什么呢？因為我在實現SharpFileDB的時候只檢測了表類型的各個PropertyInfo是否附帶[TableIndex]特性。我想，這算是人為賦予屬性的一種榮譽吧。
目前為止，這兩個坑算是最深的了。但愿它們的惡劣影響不大。
剩下的幾個坑是給SharpFileDB開發者的（目前就是我）。我會在各種可能發現bug的地方直接拋出異常。等這些throw消停了，就說明SharpFileDB穩定了。我再想個辦法把這些難看的throw收拾收拾。
總結
現在的SharpFileDB很多方面（編號、分頁、索引、查詢、塊）都受到LiteDB的啟示，再次表示感謝。
您可以（到我的Github上瀏覽此項目）。
也許我做的這個SharpFileDB很幼稚，不過我相信它可以用于實踐，我也盡量寫了注釋、提供了最簡單的使用方法，還提供了Demo。還是那句話，歡迎您指出我的代碼有哪些不足，我應該學習補充哪些知識，但請不要無意義地謾罵和人身攻擊。
文章列表
留言列表
