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

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

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

建立關(guān)系

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

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

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

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

圖1

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

圖 2

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

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

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

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

圖 3 顯示了通過網(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)是可以對關(guān)系進(jìn)行建模的方式。在圖 3 中，以前顯示為外鍵索引的關(guān)系現(xiàn)在被分解為多個(gè)指針列表，稱為集合。指針可以被視為 C 應(yīng)用程序中的 void 指針，可以直接查找堆，但堆現(xiàn)在是持久存儲。消除外鍵數(shù)據(jù)結(jié)構(gòu)和fname重復(fù)不僅減少了需要存儲的數(shù)據(jù)量，而且還減少了不必要的數(shù)據(jù)結(jié)構(gòu)維護(hù)。

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

圖 4

成本影響

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

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

添加新專輯記錄。

將新記錄設(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)，開發(fā)人員將：

1.添加新專輯記錄。

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

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

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

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

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

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

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

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

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

審核編輯：郭婷