? ? 由于項(xiàng)目里要用到mongodb，不看一下mongodb的存儲(chǔ)原理，實(shí)在是對(duì)這個(gè)之前沒了解過的數(shù)據(jù)庫不太放心，所以查了些資料學(xué)習(xí)了下。下面基于WiredTiger引擎行存儲(chǔ)做一些基本原理的說明，涉及的圖片我就不自己畫了，盜取下網(wǎng)上的圖^_^。
????首先是整體結(jié)構(gòu)，WiredTiger 數(shù)據(jù)組織方式就是 in-memory page 加 block-extent：
內(nèi)存page以B+樹的結(jié)構(gòu)組織，每個(gè)Btree節(jié)點(diǎn)為一個(gè)page，root page是btree的根節(jié)點(diǎn)，internal page是btree的中間索引節(jié)點(diǎn)，leaf page是真正存儲(chǔ)數(shù)據(jù)的葉子節(jié)點(diǎn)；btree的數(shù)據(jù)以page為單位按需從磁盤加載或?qū)懭氪疟P。
????Wiredtiger采用Copy on write（快照）的方式管理修改操作（insert、update、delete），修改操作會(huì)先緩存在cache里，checkpoint時(shí)，會(huì)產(chǎn)生一個(gè)新的root page，此時(shí)對(duì)頁面的修改會(huì)新分配索引page和數(shù)據(jù)page。原來的B+樹結(jié)構(gòu)實(shí)際成為一個(gè)快照，由后臺(tái)線程執(zhí)行checkpoint：
? ? ? Page內(nèi)部增加了多個(gè)跳表用于提升讀寫性能，通過一個(gè)實(shí)例來說明，假如一個(gè) page 存儲(chǔ)了一個(gè) [0，100] 的 key 范圍，磁盤上原來存儲(chǔ)的行 key=2， 10 ，20， 30 ， 50， 80， 90，他們的值分別是value = 102， 110， 120， 130， 150， 180， 190。在 page 數(shù)據(jù)從磁盤讀到內(nèi)存后，分別對(duì) key=20 的 value 進(jìn)行了兩次修改，兩次修改的值是分別 402，502。對(duì) key = 20 ，50 的 value 做了一次修改，修改后的 value = 122， 155，后有分配 insert 了新的 key = 3，5， 41， 99，value = 203，205，241，299。那么在內(nèi)存中的 page 就是如下圖組織數(shù)據(jù)的：
row_array：磁盤上原有 row 的位置索引數(shù)組，主要用于頁內(nèi)檢索。
row_insert_array：一個(gè)增加 kv（insert k/v）的跳表對(duì)象數(shù)組。
row_update_array：一個(gè)在 row 基礎(chǔ)上做更新（update k/v）的 value mvcc list對(duì)象素組。
page_disk： 從磁盤上讀取到的 extent 數(shù)據(jù)緩沖區(qū)，包含一個(gè) page_header 和一個(gè)數(shù)據(jù)存儲(chǔ)緩沖區(qū)（disk data）。
page disk data：存儲(chǔ)在磁盤上的 page k/v cell 行集合數(shù)據(jù)。
Page頁內(nèi)檢索時(shí)，通過row_array/insert_array/update_array 數(shù)組一一對(duì)應(yīng)的查找。
????索引說明
????往某各個(gè)集合插入多個(gè)文檔后，每個(gè)文檔在經(jīng)過底層的存儲(chǔ)引擎持久化后，會(huì)有一個(gè)位置信息，通過這個(gè)位置信息，就能從存儲(chǔ)引擎里讀出該文檔。在wiredtiger存儲(chǔ)引擎（一個(gè)KV存儲(chǔ)引擎）里，位置信息是wiredtiger在存儲(chǔ)文檔時(shí)生成的一個(gè)key，通過這個(gè)key能訪問到對(duì)應(yīng)的文檔；為方便介紹，統(tǒng)一用pos(position的縮寫)來代表位置信息。
位置信息文檔
pos1????{“name” : “jack”, “age” : 19 }
pos2????{“name” : “rose”, “age” : 20 }
pos3????{“name” : “jack”, “age” : 18 }
pos4????{“name” : “tony”, “age” : 21}
pos5????{“name” : “adam”, “age” : 18}
????假設(shè)現(xiàn)在有個(gè)查詢db.person.find( {age: 18} ), 查詢所有年齡為18歲的人，這時(shí)需要遍歷所有的文檔（『全表掃描』），根據(jù)位置信息讀出文檔，對(duì)比age字段是否為18。當(dāng)然如果只有4個(gè)文檔，全表掃描的開銷并不大，但如果集合文檔數(shù)量到百萬、甚至千萬上億的時(shí)候，對(duì)集合進(jìn)行全表掃描開銷是非常大的，一個(gè)查詢耗費(fèi)數(shù)十秒甚至幾分鐘都有可能。
????如果想加速db.person.find( {age: 18} ），就可以考慮對(duì)person表的age字段建立索引。
????db.person.createIndex( {age: 1} )// 按age字段創(chuàng)建升序索引
????建立索引后，MongoDB會(huì)額外存儲(chǔ)一份按age字段升序排序的索引數(shù)據(jù)，索引結(jié)構(gòu)類似如下，索引通常采用類似btree的結(jié)構(gòu)持久化存儲(chǔ)，以保證從索引里快速（O(logN)的時(shí)間復(fù)雜度）找出某個(gè)age值對(duì)應(yīng)的位置信息，然后根據(jù)位置信息就能讀取出對(duì)應(yīng)的文檔。
age位置信息
18????pos3
18????pos5
19????pos1
20????pos2
21????pos4
可以看到，WiredTiger索引的存儲(chǔ)結(jié)構(gòu)原理和Innodb等關(guān)系型數(shù)據(jù)庫引擎沒太大差別。
