一、問題描述
鍵值查詢是很常見的查詢場景，在資料表上建有索引後，即使表中資料記錄數巨大（幾億甚至幾十億行），用鍵值查詢出單條記錄也會很快，因為建立索引後的複雜度隻有 logN（以 2 為底）次， 10 億行資料也隻要比較 30 次（10 億約等于 2^30），在現代計算機上也隻需要數十毫秒而已。
不過，如果需要查詢的鍵值很多，比如多達幾千甚至幾萬的時候，如果每次都獨立查找，那讀取和比較也會累積到幾萬甚至幾十萬次，時間延遲由此也會漲到幾十分鐘甚至小時級别，這時候簡單地使用資料庫索引對于使用者體驗必然是難以容忍的了。
二、場景舉例
下面我們要介紹的集算器組表功能，基于高性能索引和批量鍵值查找，可以有效地應對這種場景。我們會按照以下幾種順序逐漸深入讨論：
1）單字段鍵
2）多字段鍵
3）多線程查詢
4）資料追加的處理
需要說明的，本文隻研讨單機的情況，後續還有文章會繼續深入讨論基于叢集的方案。
2.1 單字段鍵
我們以下表這種比較典型的資料結構為例：
2.1.1建立組表
首先我們建立一個組表，把源資料導入組表：
A1：建立并打開指定檔案對象，這裡的 single.ctx 是将要建立的組表檔案，擴充名用 ctx。關于組表的詳細定義和使用方法可以參考集算器教程。
A2：建立組表的資料結構為（id，data）。其中，# 開頭的字段稱為維字段，組表将假定資料按該字段有序，也就是組表 A2 将對鍵字段 id 有序。組表預設使用列存方式。
A3：假定源資料以文本方式存儲，A3 打開資料檔案。這個 txt 檔案的資料表頭以及前幾行部分資料如下圖所示。當然，源資料也可以來自資料庫等其它類型的資料源。
作者：tossman
連結：
http://c.raqsoft.com.cn/article/1536544293689來源：乾學院
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
A4：針對源資料生成遊标。其中 @t 選項指明檔案中第一行記錄是字段名。
A5：将遊标 A4 中的記錄追加寫入組表。
上面的腳本假定主鍵 id 在原始資料中已經是有序的了，如果實際情況的主鍵并非有序，那就需要先将主鍵排序後再建為組表。這時可以使用cs.sortx()函數排序，具體方法詳見函數參考。
在集算器的設計器中，通過三行代碼，可以直覺看到其中前十條資料，代碼和截圖如下所示：
A1：打開指定檔案名的組表檔案對象。
A2：f.create()，函數中無參數時則直接打開組表。
A3：使用遊标通路 A2 中的前十條資料，如下圖。
2.1.2 建立索引
接下來，我們為組表檔案建立索引，以提升檢索性能：
A2：使用無參數的 create 函數打開組表。
A3：建立索引。在函數 T.index() 中，參數 id_idx 是索引名稱，id 是維，data 是資料列。一般情況下，建索引并不需要使用資料列，在用索引查找時會到原資料表中再去找資料。不過，本例在建立索引時将資料列也包含進了索引，這樣查找時就不再引用資料列了，雖然占用的空間會大一些，但是查找的也會更快一些。
按維字段建索引時會利用組表已經有序的特點不再排序。如果開始建組表時沒有使用 #，那麼這時建索引時就會重新排序。
2.1.3查詢
使用主、子程式調用的方式來完成查詢：
查詢子程式腳本 search.dfx：
A3：keys 是參數，由下面的主程式在調用時傳遞。
A4：在組表的 icursor()這個函數中，使用索引 id_idx，以條件 A3.contain(id) 來過濾組表。集算器會自動識别出 A3.contain(id) 這個條件可以使用索引，并會自動将 A3 的内容排序後從前向後查找。
A5：将 A4 中查詢出的結果導出至 result.txt。這裡 @t 選項指定導出時将輸出字段名。
主程式腳本：
A1：從keys.txt擷取查詢鍵值序列，因為隻有一列結果，可以使用 @i 選項，将結果傳回成序列：
這個序列就是需要進行查詢的随機鍵值集。例子中使用 keys.txt 來預先存好随機的鍵值，實際應用中，也可以用其他資料源來存儲。
A2：調用子程式 serach.dfx，把 A1 獲得的鍵值集作為參數傳遞給子程式。
下面就是結果檔案 result.txt 中的部分内容：
另外，我們還可以将集算器嵌入到 Java 應用程式中，進而為 Java 應用提供靈活、簡便的資料查詢能力。嵌入時可以像用 JDBC 通路資料庫那樣通路集算器腳本。具體的寫法可以參閱教程《被 JAVA 調用》一節。
本例的單字段鍵查詢示例，在資料結構上較為簡單。其中查詢的鍵值字段為 id，需要擷取的資料為單列的 data，如果還有其它列，例如：
那麼在建立索引步驟時，就應該包含多個資料列字段，資料列參數的寫法如下所示：
在接下來要讨論的多字段鍵情況中，建索引時需要建立多個索引字段，對應參數部分也有類似的寫法：index(id_idx;id1,id2,…,idN;data1,data2,…,dataN)。
2.2多字段鍵
多字段健指的是聯合主鍵的情況，例如：
其中 type 和 id 兩個字段作為聯合主鍵确定一條記錄。
2.2.1 方法一（通用方法）
2.2.1.1 建立組表
本例中 A2 需要指定兩個維，type和 id，代碼其它部分與單字段鍵一緻。
2.2.1.2 建立索引
由于本例中有兩個維，建立索引時需要包含 type 和 id 兩個維，如 A3 所示。
2.2.1.3 查詢
A3準備了兩條資料，是由 type 和 id 構成的二進制組，作為查找的建值集，結構如下圖所示：
A4：A3.contain([type,id])，基于二進制組的序列進行資料的篩選，是以需要将 contain 函數中的參數也變為二進制組。
最終導出的結果檔案内容如下：
2.2.2 方法二（合并主鍵）
雖然多字段鍵可以直接使用，但是涉及到集合的存儲和比較都要慢一些。為了擷取高性能，更常用的辦法是把多字段鍵拼成單字段鍵。
觀察本例資料結構，雖然 type 是個串，但卻是可枚舉的，是以可以将 type 數字化後，與 id 合并為一個新的主鍵字段。而 long 類型最大值為 2^63-1，完全可以容納 id 和 type 數字化後的合并結果。我們把 type 和 id 合并後的新主鍵叫做 nid，可以按資料的規模，确定 nid 中分别用幾位代表 type 和 id。
舉例來說，id 的範圍是 9 位數，type 的枚舉個數用 3 位數表示就夠了。是以對于 nid 而言，需要 13 位（為了避免前幾位是 0，看上去不整齊，我們把第一位數字設為 1）。這樣就可以把聯合主鍵變成單字段的唯一主鍵，去掉第一位後的 12 位數，前 3 位代表數字化後的 type，後 9 位就是原來的 id。
代碼如下：
A1：type 的枚舉值組成的序列。在實際情況中，枚舉清單可能來自檔案或者資料庫資料源。。
A2：給枚舉值序列中每個 type 一個 tid。為後續的數字化主鍵合并做準備。
A3~A6：從 multi_source.txt 檔案中擷取資料，并按照 A2 中的對應關系，把 type 列的枚舉串變成數字，然後将 type 和 id 進行合并後，生成新的主鍵 nid。
A7~A8：檢視一下合并逐漸後的資料情況，跳過遊标 A4 的前 99999995 條記錄後，取 10 條記錄，結果如下：
這樣就得到了新的“單字段建”的資料結構：
接下來按照 "單字段鍵" 中的做法就可以處理了，當然還要注意確定 nid 有序。
2.3 多線程查詢
在上述方法的基礎上，我們還可以采用多線程并行方式來進一步提高性能。
所謂多線程并行，就是把資料分成 N 份，用 N 個線程查詢。但如果隻是随意地将資料分成 N 份，很可能無法真正地提高性能。因為将要查詢的鍵值集是未知的，是以理論上也無法確定希望查找的資料能夠均勻分布在每一份組表檔案中。比較好的處理方式是先觀察鍵值集的特征，進而盡可能地進行資料的均勻拆分。
比如說，繼續使用上文中多字段鍵拼成單字段鍵的例子，将合并後的主鍵 nid 對 4 取模，餘數相同的資料存在同一個組表中，最終由 4 個組表檔案裝載現有全部資料。這樣的檔案拆分方法，可以使被查詢的資料分布的相對更加均勻一些。
如果鍵值資料有比較明顯的業務特征，我們可以考慮按照實際業務場景使用日期、部門之類的字段來處理檔案拆分。如：将屬于部門 A 的 1000 條記錄均分在 10 個檔案中，每個檔案就有 100 條記錄。在利用多線程查詢屬于部門 A 的記錄時，每個線程就會從各自對應的檔案中取數相應的這 100 條記錄了。
下面我們來看個實際的例子。
2.3.1 建立組表
A1~A6：與多字段鍵的方法二一緻。
A7：使用循環函數，建立名為“鍵值名 _ 鍵值取 N 的餘數 _T.ctx”的組表檔案，其結構同為 (#nid,data)。
A8：用循環函數将遊标資料分别追加到 N 個原組表上。比如當 N=1 時，拼出的 eval 函數參數為：channel(A4).select(nid%4==0).attach(A7(1).append(~.cursor()))。意思是對遊标 A4 建立管道，将管道中記錄按鍵值 nid 取 4 的餘數，将餘數值等于 0 的記錄過濾出來。attach 是對目前管道的附加運算，表示取和目前餘數值對應的原組表，将目前管道中篩選過濾出的記錄，以遊标記錄的方式追加到 A7(1)，即第 1 個組表。
A9：循環遊标 A6，每次擷取 50 萬條記錄，直至 A6 遊标中的資料取完。
執行後，産出 4（這時例子取 N=4）個獨立的組表檔案：
2.3.2 建立建索引
A1：列出滿足 nidT.ctx 的檔案名（這裡 為通配符），這裡 @p 選項代表需要傳回帶有完整路徑資訊的檔案名。使用 fork 執行多線程時，需要注意環境中的并行限制數是否設定合理。這裡用了 4 個線程，設計器中對應的設定如下：
B2：每個線程為各個組表建立對應的索引檔案，最終結果如下：
2.3.3 查詢
A1：從 keys.txt 擷取查詢鍵值序列，因為隻有一列結果，使用 @i 選項，将結果傳回成序列：
A2：把 A1 的序列按 4 的餘數進行等值分組：
A3、B3~B5：用 fork 函數，按等值分組後的鍵值對各個組表分别并行查詢。這裡的 fork 後面分别寫了兩個參數，第一個是循環函數 N.(~-1)，第二個是 A2。在接下來的 B3、B4 中分别使用 A3(2) 和 A3(1) 來擷取 fork 後面這兩個對應順序的參數，B4：對組表檔案進行根據 B3 中的鍵值集進行資料篩選，B5：傳回遊标。由于 A3 中是多個線程傳回的遊标序列，是以 A6 中需要使用 conjx 對多個遊标進行縱向連接配接。
A6~A7：将多個線程傳回的遊标進行縱向連接配接後，導出遊标記錄至文本檔案，前幾行内容如下。
2.4 資料追加
前面我們已經解決了針對大資料的批量随機鍵值查詢問題，不過，我們不能假定資料永遠不變。尤其是對于大資料來說，新資料的追加是必然要面對的。在将新資料追加到原有組表檔案中時，我們需要讨論三種情況：有序鍵值追加、無序鍵值追加，以及資料量很大時的資料追加。
2.4.1 有序鍵值追加
單個檔案時，如果鍵值有序，追加的代碼如下：
A1：single.ctx 是已有的組表檔案，結構為 (#id,data)，其中 id 為自增鍵值。
A3~A5：新資料檔案與已有檔案結構相同，其 id 加入原組表後，對于整體資料也是有序的。這種情況可以直接追加到原組表，組表會自動更新索引。
如果按按多線程的方法拆分為多個檔案，代碼如下：
A1、A2：用遊标方式擷取新增資料。
A3：滿足通配符串："id*T.ctx"，現有 N 份組表檔案的序列。
A4、A5：與前面方法中的代碼一緻。
2.4.2 無序鍵值追加
同樣先來看一下單個檔案的追加方法，以單字段鍵為例，代碼如下：
A2：遊标方式打開現有組表。
A4：遊标方式擷取新增資料。
A5：建個新的組表檔案。
A6：在新的組表中存放現有組表資料和新增資料歸并後的結果。這裡要注意的是，用 cs.mergex(x) 進行歸并操作，需要 cs 序列對 x 有序，也就是要求組表檔案 A1 和新增資料檔案 A3 中的資料對于 id 都分别有序。若不滿足 cs 對 x 有序，程式雖然不會報錯，但是歸并出來的結果也是無序的。
當這段代碼執行完後，還需要進行舊組表、舊索引的清理以及對新組表的建立索引等操作：
前三行是檔案操作，詳見函數參考：movefile。A4 為組表建立索引，不再詳述。
下面再看看多個檔案的追加方法，以多字段鍵轉單字段鍵後的資料結構 (nid,data) 為例，代碼如下：
A3：multi_source_add.txt 是新增資料來源。
A7：假設原組表已存在，列出原組表的檔案名，依次擷取組表遊标，傳回成序列。
A8：建立新的組表檔案，用來存放舊組表資料和新增資料，在原有檔案名後加上 "_temp"，以示差別。
A9：對新增資料使用管道，将管道中的 N 份遊标記錄與對應的 N 個舊份組表中遊标記錄進行歸并，追加到新 N 份組表中。上文已有詳細的解釋。
當這段代碼執行完後，還需要進行舊組表、舊索引的清理以及對新組表的索引建立等操作，如下：
代碼中幾乎全是循環函數與簡單的檔案操作。詳見函數參考《檔案》。最後一行建立索引，前文中也已多次解釋。
2.4.3 資料量很大時的資料追加
随着新資料不斷增加，每次新追加資料與全量曆史資料歸并的時間成本将會越來越高。這時需要把每份組表檔案分為新、舊兩份，新的一份是最近一段時間内積累的追加資料，舊的是之前的曆史資料。每當有新資料需要追加時，還是按 2.4.2 的處理思路操作，但隻對新的那份組表檔案進行處理。當新份資料檔案超過一定大小門檻值（如 100G），再和舊資料合并。這樣的做法不僅可以減少歸并的時間成本，另一方面也可以降低對磁盤的損耗。
列舉的資料結構還是以 (nid,data) 為例，這次我們從頭開始完整地看一遍代碼：
首先定義新、舊組表檔案，命名規則如下：
新份組表：鍵值名 鍵值取 N 的餘數 _T.ctx；舊份組表：鍵值名 鍵值取 N 的餘數 _H.ctx。
1、 建立新、舊組表，本例中 N=4，代表建立 4 份組表：
N 取 4，生成的曆史和臨時組表檔案如下：
2、 在新組表上追加新資料。
3、 新組表合并後，清理原來的新組表和索引，然後重建新組表索引。
4、 對新資料大小進行判斷，如果超過參數 B（機關是位元組數）則與舊份組表資料合并。
5、 舊組表與新組表合并後，清理原來的舊組表和索引，然後重建舊組表索引。清理已合并的新組表，并重建空的新組表。
6、 對新、舊組表檔案分别利用多線程進行查詢
這裡需要注意 A7 中寫法，因為 B6 中傳回 B4|B5，是以導緻 A3 的結果為多個遊标序列的序列，是以在對 A3 進行縱向連接配接時，應該使用序列的 conj，而不是遊标的 conjx。
至此，基于本文的 6 個集算器腳本檔案，在第三方定時任務排程工具的合理調用下，可以實作單機情況下大資料量資料的追加，以及針對批量随機鍵值的查詢工作。