單從數據結構來看的話，我們可以這樣解釋r和d的含義。r代表著當前字段與前一字段的關系，是在哪一層合并的，即公共的父結點在哪？舉例來說，假如我們重建到了Code='en'，通過r=2可以知道是在Language那一層發(fā)生了重復。

?

為了保持原紀錄的結構，我們會保存一些NULL數據，而d就是用于重建NULL字段。通過d的值，就能知道NULL的結構。例如下圖，通過r=1知道應該合并到Name那一層。而通過d=1則知道路徑上只有一個字段，即不僅僅是Code字段不存在，Language也不存在。這樣就把NULL正確地重建出來了，那么接下來的Code='en-gb'的層級也就不會亂了。

?

然而這只是從靜態(tài)的數據結構來解釋，而r和d的深層次含義還是要看FSM是如何執(zhí)行的。真正的因果關系是FSM的執(zhí)行方式決定了數據結構的設計。

3?記錄查詢3.1?從FSM角度看r和d

先看一下前面例子的完整FSM的樣子。如果把Protocol Buffer中對數據格式定義的schema看作是編譯原理中的語法定義的話，那么一般可以使用工具如antlr,?yacc自動生成自動機，手寫的話是相當恐怖的吧。

?

?

?

對列數據的完整遍歷就是這個樣子的：

?

在討論查詢如何執(zhí)行之前，先繼續(xù)剛才未完成的題目，r和d的本質，這次通過動態(tài)的FSM的角度來分析，而不是靜態(tài)的數據結構了：

???FSM狀態(tài)機只是定義了狀態(tài)的變更，即處理流程應當如何在各個列的存儲表之間跳轉，而實際數據還是在表中保存。有點像數據庫索引，遍歷時是根據FSM進行跳轉，然后對某一列的表進行table scan。但索引是靠字段值的順序組織，因為數據庫表之間沒什么嵌套關系，而Dremel的FSM則是靠字段之間的嵌套關系來組織。

?

???狀態(tài)機中線條上的數字表示什么？回憶一下，數字表示的是：字段的數據表中當前行的下一行的r值。通過檢測下一個r值來決定跳轉。因為r=0，則說明下一行與當前行所表示的字段一定不在同一路徑，否則必然會在某一Level上有共同的字段(路徑的部分重疊)。注意這是由于Protocol Buffer的schema不是樹，沒有共同的根所導致，否則所有字段必然都會在根重復，上面對r的解釋也就沒意義了。以repeated的Forward為例，檢查到下一行r=1說明40、60都是接在20字段下面的。Code字段也是同樣道理。