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

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

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

建立關系

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

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

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

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

圖1

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

圖 2

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

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

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

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

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

圖 3

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

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

圖 4

成本影響

從一個記錄到一組記錄轉換為恒定成本。只要數(shù)據(jù)尚未駐留在數(shù)據(jù)庫 RAM 緩存中，最多只需要一個 I/O 周期。使用外鍵實現(xiàn)，在定位實際記錄之前，將首先遍歷 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)有藝術家專輯集需要采取以下步驟來完成操作：

添加新專輯記錄。

將新記錄設置為當前藝術家的所有者指針。

設置新記錄，即指向當前藝術家的前一個指針，即最后一個記錄。

將新記錄的 next 指針設置為 0。

將當前藝術家的最后一條記錄設置為指向新記錄的下一個指針。

將所有者的最后一個指針設置為新記錄。

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

1.添加新專輯記錄。

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

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

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

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

MP3 播放器基準測試

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

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

應用程序驅動數(shù)據(jù)庫決策

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

審核編輯：郭婷