內存數據庫的應用研究

【摘要】：內存數據庫是指一種將全部內容存放在內存中，而不是傳統數據庫那樣存放在外部存儲器中的數據庫。內存數據庫是當下十分火的一種NoSQL，多用于Web開發中作為緩存服務器等使用，在社交類網站也能發揮出重大作用。該設計是基于內存數據庫的核心數據算法的研究與實現。通過在Linux平臺下使用純C語言實現內存數據庫的相關核心數據結構以及算法。主要的算法有鏈表，可變字符串，字典，壓縮集合 ，壓縮列表等。

【關鍵詞】：內存數據庫；Linux平臺；鏈表；可變字符串；數據字典

1.研究內容

內存數據庫是指一種將全部內容存放在內存中，而不是傳統數據庫那樣存放在外部存儲器中的數據庫。內存數據庫所有的數據訪問控制都在內存中進行，這是與磁盤數據庫相對而言的。由于內存的讀寫速度極快，隨機訪問時間更是可以以納秒計算，所以這種數據庫的讀寫性能很高主要用于對性能的要求極高的環境中，但是在服務器關閉之后會立即丟失全部存儲的數據。內存數據庫數據結構設計與實現只能不斷的對性能不斷的提升。本設計是基于內存數據庫的核心數據算法的研究與實現。

2.鏈表

2.1鏈表list的設計

在這次的研究中，鏈表為常規性設計。用數組存儲數據的時候，數組實質上是一種線性表的順序表示方式，可以快速隨機的存儲存取線性表中的任意一個元素。但缺點是插入和刪除操作需要移動大量的數組元素，同時由于數組屬于靜態內存分配，定義數組的時候必須要指定數組的大小，而且實際使用的數組元素個數不能超過數組元素最大的長度限制，不然的話就會數據溢出，而低于所設定的數組長度，又會造成系統資源的浪費，所以，使用數組需要事先知道數據的總數，而且程序一旦運行就不能再改變這個數值，若要想改變，只能修改程序很不方便，要解決這一問題，結構體和指針配合使用表示復雜的動態數據結構是很好的解決方法，其中鏈表提供了高效的結點重新排列能力和順序性的節點訪問方式，并且可以通過增刪節點來靈活的調整鏈表的長度。

具有這樣的特點的數據可以用鏈表來保存：

1.數據是逐漸增加的

2.數據是不確定長度的，在存儲第一個數據之前很難確定將來一共需要存儲多少數據的上限，或者雖然可以確定上限，但這個上限又比通常大部分情況下數據可能達到的長度要大得多，因而一次性按照上限把空間分配好是不劃算的。而鏈表則可以在每次需要增加新數據時才為之申請內存，不會造成浪費，也不會因一次申請不足而使數據的數量受到限制。

3.希望每次添加數據、刪除數據的動作的時間復雜度都是O（1）的（常量時間）。

2.2 鏈表list的實現

每個鏈表的節點使用一個結構來進行表示，多個鏈表節點可以通過 prev 和 next 指針組成雙端鏈表。雖然只是使用多個鏈表節點 結構就可以組成鏈表， 但使用 list.h 來表示鏈表的話， 操作起來會更方便：為鏈表提供了表頭指針、表尾指針，以及鏈表長度計數器，而復制一個文件句柄的函數、 釋放鏈表內存的函數和匹配函數則是用于實現多態鏈表所需要的類型特定函數，例如：復制文件句柄的函數用于復制鏈表節點所保存的值；釋放鏈表內存的函數用于釋放鏈表節點所保存的值；匹配函數則用于對比鏈表節點所保存的值和另一個輸入值是否相等。

3可變字符串varstr

3.1可變字符串的設計

在使用傳統c語言的字符串表示數據時，c語言字符串只會作為字符串的字面數量用在一些無須對字符串的值進行修改的地方。但是我們需要的不只是一個字符串的字面數量， 而是一個可以被修改的字符串值時，構建一個可變字符串的抽象類型，并將這一個可變的字符串用作默認字符串表示。用來保存數據庫中的字符串值

3.2可變字符串的實現

在實現可變字符串的varstr.c文件中，每個varstr.h 結構表示一個可變字符串的值，釋放內存的屬性的值為0，表示這個簡單的動態字符串沒有分配任何未使用空間。長度屬性的值，表示這個可變字符串所保存的字符串的長度。緩沖區的一個數組，數組的字節分別保存了不同的字符，可變字符串遵循c字符串以空字符結尾的慣例，最后一個字節則保存了空字符＼0.

4字典dict

4.1字典的設計

哈希算法一般用于快速查詢的算法，可以將任意長度的二進制的數值對應為較為簡短的固定長度的二進制數值，這個二進制的值就是哈希值。

簡單的說，哈希算法的哈希函數可以將任意長度的輸入經過變化以后得到固定長度的輸出。哈希函數的這種單向特征和輸出數據長度固定的特征使得它可以生成消息或者數據。當要將一個新的鍵值對添加到字典里面時， 程序需要先根據鍵值對的鍵計算出哈希值和索引值， 然后再根據索引值， 將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。

4.2字典的實現

字典使用哈希表作為底層實現， 一個哈希表里面可以有多個哈希表節點， 而每個哈希表節點就保存了字典中的一個鍵值對。

（1）字典所使用哈希表

數組中的每個元素都是一個指向dict.h結構的指針， 每個字典入口結構保存著一個鍵值對。

記錄了哈希表的大小的屬性， 也就是數組的大小， 在用一個專門的屬性記錄了哈希表目前已有節點（鍵值對）的數量。

再有一個表面屬性 ，這個屬性和哈希值一起決定一個鍵應該被放到數組的哪個索引上面。

（2）哈希表的每個節點都保存著一個鍵值對：

其中一個哈希表節點的指針，可以將多個哈希值相同的鍵值對連接在一次， 以此來解決鍵沖突的問題。

（3）字典由 dict.h結構表示：

針對不同類型的鍵值對， 為創建多態字典而設置類型屬性，類型屬性是一個指向字典類型結構的指針， 每個字典類型結構保存了一簇用于操作特定類型鍵值對的函數。

5壓縮集合zipset

5.1壓縮集合的設計

壓縮集合用于保存整數值得集合抽象數據結構，可以保存int型的整數值，而且可以保證集合中不會出現重復元素。當一個集合只包含整數值元素，并且這個集合的元素數量不多的時候，就可以是使用壓縮集合作為集合鍵的底層結構。

5.1壓縮集合的實現

在壓縮集合代碼實現的zipset.c文件中，每個壓縮集合，長度屬性記錄整數集合的包含的元素個數也就是數組的長度，數組的類型取決于編碼屬性的值。

6壓縮列表ziplist

6.1壓縮列表的設計

壓縮列表是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只包含少量列表項， 并且每個列表項要么就是小整數值， 要么就是長度比較短的字符串， 那么就會使用壓縮列表來做列表鍵的底層實現。

6.2壓縮列表的實現

一個壓縮列表可以包含任意多個節點， 每個節點可以保存一個字節數組或者一個整數值。整個壓縮列表的組成包括記錄整個壓縮列表占用內存字節數的屬性；記錄壓縮列表表尾節點距離壓縮列表的起始地址有多少字節的屬性，通過這個偏移量，就可以不用遍歷整個壓縮列表就可以確定表尾節點的地址；記錄壓縮列表包含節點數量的屬性；以及用于標記壓縮列表的末端的屬性。

7 結束語

內存數據庫在軟件系統開發中的應用，極大地提高系統運行的處理能力，內存數據庫，通過避開磁盤的耗時操作，內存優化的索引結構快速的日志和恢復，高并發的事務處理，達到了高性能的數據管理能力，低成本的基礎上大大提高系統的處理能力。大量的數據操作通過內存數據庫集中管理，也增強了系統開發中的擴展能力。

參考文獻：

[1] 張曉偉.探討分布式內存數據庫的設計與應用[J].硅谷， 2009（03）

[2] 王慧嬪.基于MMDB技術對電信計費系統研究與實現的探討[J].科技資訊， 2009（16）

[3] 王金華，江水，吳嫻，盧瑤，龍剛.輕量級內存數據庫的研究[J].計算機工程， 2008（S1）

[4] 王珊，肖艷芹，劉大為，覃雄派.內存數據庫關鍵技術研究[J].計算機應用， 2007（10）

[5] 朱勇，張炯，沈軼.內存數據庫在移動計費系統中的應用[J].現代機械， 2007（05）