在這一章，我們将了解LiteDB裡面幾個基本資料結構包括索引結構和資料塊結構，我也會試着說明前輩資料之巅在部落格中遇到的問題，最後對比mysql進一步深入了解LiteDB的索引原理。
1.LiteDB的五種基本資料結構
在LiteDB的Structures中定義了五個基本資料結構，分别為PageAddress、CollectionIndex、DataBlock、IndexNode和IndexKey。他們各自說明如下：
1.1 PageAddress
頁位址，代表一個資料在頁的位置。其中的PageID就是頁的ID，Index是資料頁或者索引頁中字典的key值。根據頁的ID和字典key值，就可以找到相應的IndexNode或者DataBlock。将PageID=uint.MaxValue和Index= ushort.MaxValue的頁位址作為空頁。
1.2 CollectionIndex
表索引，類似于mysql将表的字段設定為一個索引。屬性Field表示存入的字段名稱，屬性Unique用于辨別是否是非重複字段。
1.3 DataBlock
資料塊，這個類中Position就是存放在DataPage中的字典索引，比如一個Customer{ID=1，Name=“Jim1”，age=100}，将這條記錄處理成byte數組也就是屬性Data，将該資料塊存進DataPage中的字典中，在放入字典的同時，将生成一個key值。DataPage的PageID和字典的key值就作為這個資料塊的Position。
IndexRef是一個頁位址數組，存儲的是索引頁的位置。ExtendPageID是指擴充頁的ID。Key是這條記錄的主鍵。
1.4 IndexKey
索引鍵值，這個結構體實作了IComparable接口，主要完成的作用就是将常見的資料類型比如int、byte、string、DateTime轉換為統一一個資料類型，然後進行比較。
1.5 IndexNode
索引節點，用來存儲一條記錄的索引。索引節點之間用跳表來組成資料結構。
注意：屬性Position是存放在IndexPage中的字典索引，而DataBlock是存放在DataPage頁中字典索。屬性Prev和Next分别是指向上一個和下一個節點的IndexPage頁位址數組。
2. 舉例說明
下面用一個示例來說明索引頁、資料頁和資料塊之間的關系，我建立一個"customer"的表，字段為{“Id”,"Age","Name",}，然後插入10記錄：{Id=1,Age=1,Name="Jim_1"},{Id=2,Age=2,Name="Jim_2"}.....{Id=10,Age=10,Name="Jim_10"}。大家可以看一下目前的資料展示如下：
從上面可以清楚看到IndexPage裡面的IndexNode是有序排列。我們學過排序算法肯定都知道，要想實作排序，必須有比較對象。是以Key就要實作一個IComparable接口，這樣所有的IndexNode就可以通過他們的Key值進行排序。對IndexNode的增删改查是用跳表這種資料結構，後面有機會我會專門結合LiteDB講一下跳表這種資料結構。同時要注意的是IndexNode的連結有Next和Prev，我這裡為了簡略，隻繪制出Next的連結。
我們能看到目前隻有一頁DataPage，這頁DataPage的ItemCount是10，正好對應了10條資料。我再用PPT的模式将IndexNode，DataBlock的關系描述如下：
上面這張圖就将IndexNode和DataBlock之間關系描述出來了，兩個不同的IndexPage中的索引節點指向的是同一個DataPage中的DataBlock。同時請各位注意的是，由于插入的Age是數值，Name是字元串，是以他們各自在索引頁裡面的排列順序肯定是不一樣的。
3.針對部落客資料之巅的疑問
部落客資料之巅在分頁問題上做了一些嘗試，嘗試過程中遇到了查詢出來的資料ID并不是按順序排列的問題，我這裡截圖如下：
為什麼查詢出來的ID沒有按序排列，這是因為執行n.Name.StartWith("Jim1")的linq語句時，LiteDB就從Field為Name的IndexPage中進行查詢，這個IndexPage中的Key裝的是字元串變量，那麼進行比較的也是字元串。做個簡單實驗我們就能知道“Jim_1”<"Jim_11"<"Jim_2"，這樣索引對應的資料查詢出來的id就是1,11,2這種順序了。
4.對比Mysql
如果大家對mysql的索引稍微有些了解的話，應該知道mysql的索引資料結構使用的是B+樹，mysql有兩種主要的存儲引擎叫做InnoDB和MyISM（下面内容轉自部落格https://www.cnblogs.com/shijingxiang/articles/4743324.html）。
InnoDB使用的是聚簇索引，将主鍵組織到一棵B+樹中，而行資料就儲存在葉子節點上，若使用"where id = 14"這樣的條件查找主鍵，則按照B+樹的檢索算法即可查找到對應的葉節點，之後獲得行資料。若對Name列進行條件搜尋，則需要兩個步驟：第一步在輔助索引B+樹中檢索Name，到達其葉子節點擷取對應的主鍵。第二步使用主鍵在主索引B+樹種再執行一次B+樹檢索操作，最終到達葉子節點即可擷取整行資料。
MyISAM使用的是非聚簇索引，非聚簇索引的兩棵B+樹看上去沒什麼不同，節點的結構完全一緻隻是存儲的内容不同而已，主鍵索引B+樹的節點存儲了主鍵，輔助鍵索引B+樹存儲了輔助鍵。表資料存儲在獨立的地方，這兩顆B+樹的葉子節點都使用一個位址指向真正的表資料，對于表資料來說，這兩個鍵沒有任何差别。由于索引樹是獨立的，通過輔助鍵檢索無需通路主鍵的索引樹。
一個表如下圖存儲了4行資料。其中Id作為主索引，Name作為輔助索引。圖示清晰的顯示了聚簇索引和非聚簇索引的差異。
1 由于行資料和葉子節點存儲在一起，這樣主鍵和行資料是一起被載入記憶體的，找到葉子節點就可以立刻将行資料傳回了，如果按照主鍵Id來組織資料，獲得資料更快。
2 輔助索引使用主鍵作為"指針" 而不是使用位址值作為指針的好處是，減少了當出現行移動或者資料頁分裂時輔助索引的維護工作，使用主鍵值當作指針會讓輔助索引占用更多的空間，換來的好處是InnoDB在移動行時無須更新輔助索引中的這個"指針"。也就是說行的位置（實作中通過16K的Page來定位，後面會涉及）會随着資料庫裡資料的修改而發生變化（前面的B+樹節點分裂以及Page的分裂），使用聚簇索引就可以保證不管這個主鍵B+樹的節點如何變化，輔助索引樹都不受影響。
最後我們可以看到LiteDB的索引方式和MyISAM類似,不管是主鍵索引還是輔助索引指向的是資料的位址，隻不過LiteDB索引内部是用跳表，而mysql用的是B+樹。
轉載于:https://www.cnblogs.com/xiaozhangStudent/p/11024586.html