嵌入式數(shù)據(jù)庫(kù)為什么不使用關(guān)系數(shù)據(jù)模型

以傳統(tǒng)方式處理數(shù)據(jù)管理并不總是能很好地應(yīng)用于嵌入式系統(tǒng)。關(guān)系數(shù)據(jù)庫(kù)模型的流行是無(wú)可爭(zhēng)辯的，但這并不意味著它是處理寶貴的 CPU、內(nèi)存和存儲(chǔ)資源時(shí)的正確選擇。關(guān)系模型的一種替代方法可以幫助降低硬件要求并為復(fù)雜的數(shù)據(jù)關(guān)系建模，從而允許供應(yīng)商為手頭的應(yīng)用程序釋放資源。

在競(jìng)爭(zhēng)日益激烈的市場(chǎng)中，嵌入式應(yīng)用程序供應(yīng)商不斷尋找新方法來(lái)降低應(yīng)用程序成本和上市時(shí)間，并增加應(yīng)用程序功能以最終獲得市場(chǎng)份額并促進(jìn)產(chǎn)品銷售。雖然收入利潤(rùn)率受到擠壓，但消費(fèi)者期望新產(chǎn)品發(fā)布具有更高的質(zhì)量和功能。供應(yīng)商越來(lái)越愿意將第三方組件添加到新產(chǎn)品和現(xiàn)有產(chǎn)品中，以實(shí)現(xiàn)這些目標(biāo)。

任何嵌入式應(yīng)用程序中的一個(gè)重要組成部分是高效的數(shù)據(jù)管理。商業(yè)嵌入式數(shù)據(jù)管理引擎正在獲得認(rèn)可，并且在許多情況下成為應(yīng)用程序的硬性要求。在過(guò)去的 25 年中，隨著數(shù)百萬(wàn)美元的投入用于研發(fā)，關(guān)系模型已成為數(shù)據(jù)管理的首選方法。

建立關(guān)系

關(guān)系數(shù)據(jù)模型的首要好處不是模型本身，而是它與 SQL 語(yǔ)言的密切關(guān)系。SQL 有兩個(gè)主要好處：

即席查詢：使用預(yù)定義的關(guān)系數(shù)據(jù)模型，任何有效的 SQL 都將保證結(jié)果而不保證其性能。在數(shù)據(jù)挖掘應(yīng)用程序中，這是一個(gè)非常強(qiáng)大的功能，但在大多數(shù)嵌入式應(yīng)用程序中，用例和查詢?cè)谠O(shè)計(jì)時(shí)是已知的。想想 MP3 播放器：所有用例，例如音樂(lè)文件同步和用戶導(dǎo)航，都是預(yù)定義的，在設(shè)備或固件的下一個(gè)版本發(fā)布之前不會(huì)改變。這不像經(jīng)理會(huì)來(lái)要求開(kāi)發(fā)人員根據(jù)現(xiàn)有數(shù)據(jù)模型創(chuàng)建新報(bào)告。

供應(yīng)商獨(dú)立性： SQL 是許多嵌入式數(shù)據(jù)庫(kù)供應(yīng)商支持的通用語(yǔ)言。據(jù)推測(cè)，用另一個(gè)替換一個(gè)應(yīng)該像打開(kāi)電燈開(kāi)關(guān)一樣容易。盡管它并不那么簡(jiǎn)單，但進(jìn)行這種轉(zhuǎn)換絕對(duì)比從一個(gè)專有 API 遷移到另一個(gè)更容易。

關(guān)系模型通過(guò)值匹配以及在大多數(shù)情況下通過(guò)鍵來(lái)建立記錄之間的關(guān)系。這些鍵稱為主鍵/外鍵關(guān)系。圖 1 說(shuō)明了 MP3 播放器中藝術(shù)家和專輯的關(guān)系模型，它將作為本文進(jìn)一步討論的基礎(chǔ)。

圖1

仔細(xì)觀察，關(guān)系是通過(guò)將 fname 的值復(fù)制到專輯表中并在兩者之間添加索引結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。復(fù)制 fname 字段本身會(huì)增加數(shù)據(jù)庫(kù)映像的開(kāi)銷。圖 1 中的另一個(gè)含義與外鍵有關(guān)。如果沒(méi)有添加外鍵數(shù)據(jù)結(jié)構(gòu)，開(kāi)發(fā)人員每次處理關(guān)系時(shí)都必須訪問(wèn)專輯表中的每一行。原因是表格數(shù)據(jù)沒(méi)有任何順序，因此無(wú)法判斷匹配值是在表格的開(kāi)頭、中間和/或結(jié)尾。添加外鍵索引解決了這個(gè)表掃描問(wèn)題。圖 2 分解了外鍵索引和專輯表來(lái)說(shuō)明索引開(kāi)銷。

圖 2

有了 B 樹，開(kāi)發(fā)人員可以進(jìn)行二分搜索來(lái)建立關(guān)系，從表掃描到索引掃描。這將線性搜索轉(zhuǎn)換為二分搜索，通過(guò)指數(shù)差異提高了運(yùn)行關(guān)系的成本。

表掃描的成本為 O（n），其中 n 表示表中的記錄數(shù)，而索引掃描的成本為 O（log n）。在計(jì)算復(fù)雜性理論中，大 O 符號(hào)經(jīng)常用于描述輸入數(shù)據(jù)的大小如何影響算法——計(jì)算資源的使用。其他明顯的影響包括表示索引所需的空間以及在數(shù)據(jù)更改時(shí)維護(hù)此結(jié)構(gòu)所需的命中率。由于從時(shí)間、CPU 和功耗方面來(lái)看，I/O 是最昂貴的操作，因此開(kāi)發(fā)人員應(yīng)該努力減少它。對(duì)于閃存等存儲(chǔ)設(shè)備，寫入也應(yīng)受到限制，以防止對(duì)該技術(shù)施加的最大寫入擦除周期和空間回收周期產(chǎn)生負(fù)面影響。

那么問(wèn)題就變成了：開(kāi)發(fā)人員如何以低于 O（log n） 的成本維護(hù)這種關(guān)系信息？

重新引入網(wǎng)絡(luò)數(shù)據(jù)模型

圖 3 顯示了通過(guò)網(wǎng)絡(luò)數(shù)據(jù)模型調(diào)整的相同數(shù)據(jù)表示。

圖 3

網(wǎng)絡(luò)數(shù)據(jù)模型早于關(guān)系模型，可以看作是它的超集。這意味著在關(guān)系模型中表達(dá)的任何東西都可以在網(wǎng)絡(luò)模型中表達(dá)，甚至 SQL 支持。主要優(yōu)點(diǎn)是可以對(duì)關(guān)系進(jìn)行建模的方式。在圖 3 中，以前顯示為外鍵索引的關(guān)系現(xiàn)在被分解為多個(gè)指針列表，稱為集合。指針可以被視為 C 應(yīng)用程序中的 void 指針，可以直接查找堆，但堆現(xiàn)在是持久存儲(chǔ)。消除外鍵數(shù)據(jù)結(jié)構(gòu)和fname重復(fù)不僅減少了需要存儲(chǔ)的數(shù)據(jù)量，而且還減少了不必要的數(shù)據(jù)結(jié)構(gòu)維護(hù)。

圖中簡(jiǎn)化了一個(gè)所有者有兩個(gè)指針，第一個(gè)和最后一個(gè)成員記錄，而成員有三個(gè)，所有者加上前一個(gè)和下一個(gè)成員。根據(jù)指針的本質(zhì)，它不與任何特定的數(shù)據(jù)類型綁定，因此關(guān)系可以對(duì)任意數(shù)量的記錄類型之間的復(fù)雜關(guān)系進(jìn)行建模，而不僅僅是關(guān)系模型強(qiáng)加的兩個(gè)之間的關(guān)系。本文不會(huì)討論復(fù)雜的建模功能，但它說(shuō)明了網(wǎng)絡(luò)模型的靈活性。

圖 4

成本影響

從一個(gè)記錄到一組記錄轉(zhuǎn)換為恒定成本。只要數(shù)據(jù)尚未駐留在數(shù)據(jù)庫(kù) RAM 緩存中，最多只需要一個(gè) I/O 周期。使用外鍵實(shí)現(xiàn)，在定位實(shí)際記錄之前，將首先遍歷 B 樹，成本為 O（log n）。很明顯，遍歷 B 樹有 CPU 和 I/O 開(kāi)銷，但也有內(nèi)存開(kāi)銷。任何數(shù)據(jù)庫(kù)緩存都會(huì)存儲(chǔ)最近訪問(wèn)過(guò)的數(shù)據(jù)，甚至是 B-tree 數(shù)據(jù)。由于 B-tree 掃描最終在緩存中，因此緩存必須很大，否則需要額外的 I/O 來(lái)刷新其數(shù)據(jù)。

寫操作也需要恒定的成本。開(kāi)發(fā)人員將新記錄添加到專輯表并將新記錄加入現(xiàn)有藝術(shù)家專輯集需要采取以下步驟來(lái)完成操作：

添加新專輯記錄。

將新記錄設(shè)置為當(dāng)前藝術(shù)家的所有者指針。

設(shè)置新記錄，即指向當(dāng)前藝術(shù)家的前一個(gè)指針，即最后一個(gè)記錄。

將新記錄的 next 指針設(shè)置為 0。

將當(dāng)前藝術(shù)家的最后一條記錄設(shè)置為指向新記錄的下一個(gè)指針。

將所有者的最后一個(gè)指針設(shè)置為新記錄。

在這一系列操作期間不進(jìn)行掃描，導(dǎo)致成本不變。使用 B-tree 實(shí)現(xiàn)，開(kāi)發(fā)人員將：

1.添加新專輯記錄。

2. 掃描 B-tree 找到新記錄的索引位置。

3.如果B-tree中沒(méi)有空間，則拆分并重組樹。

4. 在 B 樹中寫入對(duì)新記錄的引用。

在此序列中，開(kāi)發(fā)人員在步驟 2 中遇到 O（log n） 成本。更重要的是，步驟 3 可能會(huì)通過(guò)要求重新組織部分或整個(gè)樹而產(chǎn)生巨大的成本。重組是不可預(yù)測(cè)的，因?yàn)樗Q于樹的完整性以及必須在樹中的哪個(gè)位置進(jìn)行更改。包含數(shù)據(jù)的節(jié)點(diǎn)越多，重組的機(jī)會(huì)就越大。在大多數(shù)情況下，B-tree 更改是在本地完成的，只影響少數(shù)幾個(gè)節(jié)點(diǎn)，但有時(shí)會(huì)觸及許多節(jié)點(diǎn)，給應(yīng)用程序增加了不確定性。因此，如果開(kāi)發(fā)人員發(fā)現(xiàn)自己需要可預(yù)測(cè)的性能，他們應(yīng)該檢查他們的數(shù)據(jù)是如何表示的。

MP3 播放器基準(zhǔn)測(cè)試

那么開(kāi)發(fā)者使用網(wǎng)絡(luò)模型可以節(jié)省多少硬件資源呢？在一個(gè)示例中，Birdstep Technology 實(shí)施了藝術(shù)家-》專輯-》歌曲的三向關(guān)系，允許商業(yè) MP3 播放器制造商獲得一些關(guān)于資源節(jié)約的確鑿事實(shí)。開(kāi)發(fā)人員仔細(xì)比較了 Birdstep Technology 的 RDM Embedded 數(shù)據(jù)庫(kù)引擎，它是一種網(wǎng)絡(luò)模型，以及使用臺(tái)式計(jì)算機(jī)和消費(fèi)電子硬件的公共領(lǐng)域關(guān)系數(shù)據(jù)庫(kù)引擎。如表 1 所示，硬件資源受限越多，節(jié)省的差異就越大。

在這兩種硬件解決方案上，網(wǎng)絡(luò)模型用于存儲(chǔ)相同數(shù)量的記錄和關(guān)系的磁盤空間減少了 27%。所有的存儲(chǔ)節(jié)省都可以歸功于用指針替換了藝術(shù)家-》專輯和專輯-》歌曲的外鍵索引。刪除這些數(shù)據(jù)結(jié)構(gòu)對(duì)存儲(chǔ)需求產(chǎn)生了巨大影響。B 樹索引通常需要 1.3 倍于它的索引空間。

應(yīng)用程序驅(qū)動(dòng)數(shù)據(jù)庫(kù)決策

在尋求在應(yīng)用程序中添加或替換現(xiàn)有數(shù)據(jù)管理組件時(shí)，開(kāi)發(fā)人員應(yīng)仔細(xì)考慮選擇。應(yīng)用程序應(yīng)該推動(dòng)決策，而不是行業(yè)。有幾種不同的解決方案可用，從簡(jiǎn)單的庫(kù)到完整的客戶端服務(wù)器解決方案，增加了本文所述的功能。選擇正確的技術(shù)并對(duì)數(shù)據(jù)進(jìn)行正確建?？梢詫?duì)應(yīng)用程序的成本產(chǎn)生巨大影響，從而帶來(lái)更高的利潤(rùn)率、更高質(zhì)量的產(chǎn)品和更好的最終用戶體驗(yàn)。

審核編輯：郭婷