設計key-value數據的存儲查詢模塊
（百度2011）單機存儲100億大數據量的key-value數據，要求能夠支持插入和查詢操作，單條數據長度不定，平均約1024字節，假設可用內存10G，磁盤空間不限，請設計一個存儲查詢模塊，支持按照key來獲取對應的value，設計目標以查詢性能為先，盡量節約資源，查詢可以理解為網民的檢索行為。
1) 說明該設計方案和主要思路，以及優缺點
2) 請詳細說明該設計思路下查詢和插入的操作流程
3) 如果增加更新操作，請評估前面的設計方案是否可行，需要做怎樣的修改，不可行則指明主要問題點。
分析：
1)數據量大小為：
data_size=100億*1024Byte=10^10*10^3Byte=10^13Byte=10^4G
假設每個key的長度不超過128Byte。
使用2種文件存儲數據：索引文件和數據文件。
索引文件采用類似B+樹的結構化存儲，一條數據對應一條記錄，一條記錄包括：數據的key、存儲該數據的數據文件ID以及數據文件偏移量，占用空間:
record_size=key_size+data_file_ID_size+offset_size=128+4+8=140Byte。
B+樹共有3層，內節點只存儲最多M個關鍵字key和相應的M棵子樹的位置，第i個關鍵字是第i棵子樹中的最小關鍵字，葉節點存儲最多M個key-value數據。每個節點最多包含M個key，M^3=100億=10^10，M=2200。
內節點有2種形式：一是存儲在索引文件中，包含的域有：關鍵字key，相應的子節點的索引文件ID和文件偏移量，占用空間：
inner_node_size_in_file=(key_size+index_file_ID_size+file_offset_size)*M=(128+4+8)*2200
=30800Byte=300K。
二是存儲在內存中，除了上面提到的域，還包括指向子節點的指針域，占用空間：
Inner_node_size_in_memory*M=(inner_node_size_in_file+pointer_size)*M
=144*2200Byte=316800Byte=310K。
第一層和第二層占用空間：
(M+1)*inner_node_size_in_momery=666M，
可以全部存儲在內存中。
內節點按順序寫入索引文件，采用惰性空間分配策略，即使內節點沒有滿，也分配最大空間inner_node_size_in_file。這樣保證內節點可以在原地更新，保持有序狀態。假設索引文件最大index_file_size=2G，一個索引文件可以容納內節點數目：
Inner_count_in_file=index_file_size/ inner_node_size_in_momery
=6990>inner_node_count=M+1
一個索引文件足夠了。
葉節點包含key-value數據，占用空間：
Leaf_size_in_memory=M*data_size=2200*1024=2200K
葉節點以在文件尾追加方式寫入數據文件，不需要保持有序，因為B+樹的第二層內節點記錄了所有葉節點的數據文件ID和文件偏移量。假設一個數據文件大小是data_file_size=2G，數據文件數目為
data_file_count=data_size/data_file_size=5000
優點：
1) B+樹采用3層，第1層和第2層是內節點，是索引節點，存儲在索引文件，可以全部存儲在內存，第3層是葉節點，存儲在數據文件，部分緩存在內存。插入和查找一條數據，最多需要訪問硬盤一次。
2) 索引文件采用惰性空間分配策略保證內節點可以在原地更新，保持有序狀態。
3) 數據文件的更新一直是在尾部追加，不需要移動數據。
缺點：
1) 索引文件浪費了部分空間。
第二問：
查找：在根節點二叉查找關鍵字，下降到第二層某一個節點，二叉查找關鍵字，下降到第三層某一個關鍵字，若該條數據不在內存中，從數據文件讀入，若在內存中，直接返回數據。
插入：與查找類似，找到該條數據應該在的位置，添加到最后一個數據文件的末尾。
第三問：若增加更新操作，前面的方案可行，需要做下列修改：
將數據按照大小分類存儲到不同的數據文件中。假設數據大小平均分布在512Byte到1536Byte之間，步長平均為128Byte，數據文件分類為存儲512Byte的，存儲512+128Byte的，存儲512+128*2Byte的，……，類似內存池的做法。更新數據時，將數據寫到能容納該條數據的最小分類的數據文件，將該位置記為空閑，加到該數據文件的空閑位置鏈表。鏈表的指針可以用空閑位置的前4個字節表示，文件的最開始4個字節表示鏈表頭部指針。當然，這樣會浪費部分空間。可以監控每種文件的空間使用情況，做出調整。