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

?

為了保持原紀(jì)錄的結(jié)構(gòu)，我們會(huì)保存一些NULL數(shù)據(jù)，而d就是用于重建NULL字段。通過(guò)d的值，就能知道NULL的結(jié)構(gòu)。例如下圖，通過(guò)r=1知道應(yīng)該合并到Name那一層。而通過(guò)d=1則知道路徑上只有一個(gè)字段，即不僅僅是Code字段不存在，Language也不存在。這樣就把NULL正確地重建出來(lái)了，那么接下來(lái)的Code='en-gb'的層級(jí)也就不會(huì)亂了。

?

然而這只是從靜態(tài)的數(shù)據(jù)結(jié)構(gòu)來(lái)解釋，而r和d的深層次含義還是要看FSM是如何執(zhí)行的。真正的因果關(guān)系是FSM的執(zhí)行方式?jīng)Q定了數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。

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

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

?

?

?

對(duì)列數(shù)據(jù)的完整遍歷就是這個(gè)樣子的：

?

在討論查詢?nèi)绾螆?zhí)行之前，先繼續(xù)剛才未完成的題目，r和d的本質(zhì)，這次通過(guò)動(dòng)態(tài)的FSM的角度來(lái)分析，而不是靜態(tài)的數(shù)據(jù)結(jié)構(gòu)了：

???FSM狀態(tài)機(jī)只是定義了狀態(tài)的變更，即處理流程應(yīng)當(dāng)如何在各個(gè)列的存儲(chǔ)表之間跳轉(zhuǎn)，而實(shí)際數(shù)據(jù)還是在表中保存。有點(diǎn)像數(shù)據(jù)庫(kù)索引，遍歷時(shí)是根據(jù)FSM進(jìn)行跳轉(zhuǎn)，然后對(duì)某一列的表進(jìn)行table scan。但索引是靠字段值的順序組織，因?yàn)閿?shù)據(jù)庫(kù)表之間沒(méi)什么嵌套關(guān)系，而Dremel的FSM則是靠字段之間的嵌套關(guān)系來(lái)組織。

?

???狀態(tài)機(jī)中線條上的數(shù)字表示什么？回憶一下，數(shù)字表示的是：字段的數(shù)據(jù)表中當(dāng)前行的下一行的r值。通過(guò)檢測(cè)下一個(gè)r值來(lái)決定跳轉(zhuǎn)。因?yàn)閞=0，則說(shuō)明下一行與當(dāng)前行所表示的字段一定不在同一路徑，否則必然會(huì)在某一Level上有共同的字段(路徑的部分重疊)。注意這是由于Protocol Buffer的schema不是樹(shù)，沒(méi)有共同的根所導(dǎo)致，否則所有字段必然都會(huì)在根重復(fù)，上面對(duì)r的解釋也就沒(méi)意義了。以repeated的Forward為例，檢查到下一行r=1說(shuō)明40、60都是接在20字段下面的。Code字段也是同樣道理。