內(nèi)存數(shù)據(jù)庫(kù)的應(yīng)用研究

【摘要】：內(nèi)存數(shù)據(jù)庫(kù)是指一種將全部?jī)?nèi)容存放在內(nèi)存中，而不是傳統(tǒng)數(shù)據(jù)庫(kù)那樣存放在外部存儲(chǔ)器中的數(shù)據(jù)庫(kù)。內(nèi)存數(shù)據(jù)庫(kù)是當(dāng)下十分火的一種NoSQL，多用于Web開(kāi)發(fā)中作為緩存服務(wù)器等使用，在社交類網(wǎng)站也能發(fā)揮出重大作用。該設(shè)計(jì)是基于內(nèi)存數(shù)據(jù)庫(kù)的核心數(shù)據(jù)算法的研究與實(shí)現(xiàn)。通過(guò)在Linux平臺(tái)下使用純C語(yǔ)言實(shí)現(xiàn)內(nèi)存數(shù)據(jù)庫(kù)的相關(guān)核心數(shù)據(jù)結(jié)構(gòu)以及算法。主要的算法有鏈表，可變字符串，字典，壓縮集合 ，壓縮列表等。

【關(guān)鍵詞】：內(nèi)存數(shù)據(jù)庫(kù)；Linux平臺(tái)；鏈表；可變字符串；數(shù)據(jù)字典

1.研究?jī)?nèi)容

內(nèi)存數(shù)據(jù)庫(kù)是指一種將全部?jī)?nèi)容存放在內(nèi)存中，而不是傳統(tǒng)數(shù)據(jù)庫(kù)那樣存放在外部存儲(chǔ)器中的數(shù)據(jù)庫(kù)。內(nèi)存數(shù)據(jù)庫(kù)所有的數(shù)據(jù)訪問(wèn)控制都在內(nèi)存中進(jìn)行，這是與磁盤(pán)數(shù)據(jù)庫(kù)相對(duì)而言的。由于內(nèi)存的讀寫(xiě)速度極快，隨機(jī)訪問(wèn)時(shí)間更是可以以納秒計(jì)算，所以這種數(shù)據(jù)庫(kù)的讀寫(xiě)性能很高主要用于對(duì)性能的要求極高的環(huán)境中，但是在服務(wù)器關(guān)閉之后會(huì)立即丟失全部存儲(chǔ)的數(shù)據(jù)。內(nèi)存數(shù)據(jù)庫(kù)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)只能不斷的對(duì)性能不斷的提升。本設(shè)計(jì)是基于內(nèi)存數(shù)據(jù)庫(kù)的核心數(shù)據(jù)算法的研究與實(shí)現(xiàn)。

2.鏈表

2.1鏈表list的設(shè)計(jì)

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

具有這樣的特點(diǎn)的數(shù)據(jù)可以用鏈表來(lái)保存：

1.數(shù)據(jù)是逐漸增加的

2.數(shù)據(jù)是不確定長(zhǎng)度的，在存儲(chǔ)第一個(gè)數(shù)據(jù)之前很難確定將來(lái)一共需要存儲(chǔ)多少數(shù)據(jù)的上限，或者雖然可以確定上限，但這個(gè)上限又比通常大部分情況下數(shù)據(jù)可能達(dá)到的長(zhǎng)度要大得多，因而一次性按照上限把空間分配好是不劃算的。而鏈表則可以在每次需要增加新數(shù)據(jù)時(shí)才為之申請(qǐng)內(nèi)存，不會(huì)造成浪費(fèi)，也不會(huì)因一次申請(qǐng)不足而使數(shù)據(jù)的數(shù)量受到限制。

3.希望每次添加數(shù)據(jù)、刪除數(shù)據(jù)的動(dòng)作的時(shí)間復(fù)雜度都是O（1）的（常量時(shí)間）。

2.2 鏈表list的實(shí)現(xiàn)

每個(gè)鏈表的節(jié)點(diǎn)使用一個(gè)結(jié)構(gòu)來(lái)進(jìn)行表示，多個(gè)鏈表節(jié)點(diǎn)可以通過(guò) prev 和 next 指針組成雙端鏈表。雖然只是使用多個(gè)鏈表節(jié)點(diǎn) 結(jié)構(gòu)就可以組成鏈表， 但使用 list.h 來(lái)表示鏈表的話， 操作起來(lái)會(huì)更方便：為鏈表提供了表頭指針、表尾指針，以及鏈表長(zhǎng)度計(jì)數(shù)器，而復(fù)制一個(gè)文件句柄的函數(shù)、 釋放鏈表內(nèi)存的函數(shù)和匹配函數(shù)則是用于實(shí)現(xiàn)多態(tài)鏈表所需要的類型特定函數(shù)，例如：復(fù)制文件句柄的函數(shù)用于復(fù)制鏈表節(jié)點(diǎn)所保存的值；釋放鏈表內(nèi)存的函數(shù)用于釋放鏈表節(jié)點(diǎn)所保存的值；匹配函數(shù)則用于對(duì)比鏈表節(jié)點(diǎn)所保存的值和另一個(gè)輸入值是否相等。

3可變字符串varstr

3.1可變字符串的設(shè)計(jì)

在使用傳統(tǒng)c語(yǔ)言的字符串表示數(shù)據(jù)時(shí)，c語(yǔ)言字符串只會(huì)作為字符串的字面數(shù)量用在一些無(wú)須對(duì)字符串的值進(jìn)行修改的地方。但是我們需要的不只是一個(gè)字符串的字面數(shù)量， 而是一個(gè)可以被修改的字符串值時(shí)，構(gòu)建一個(gè)可變字符串的抽象類型，并將這一個(gè)可變的字符串用作默認(rèn)字符串表示。用來(lái)保存數(shù)據(jù)庫(kù)中的字符串值

3.2可變字符串的實(shí)現(xiàn)

在實(shí)現(xiàn)可變字符串的varstr.c文件中，每個(gè)varstr.h 結(jié)構(gòu)表示一個(gè)可變字符串的值，釋放內(nèi)存的屬性的值為0，表示這個(gè)簡(jiǎn)單的動(dòng)態(tài)字符串沒(méi)有分配任何未使用空間。長(zhǎng)度屬性的值，表示這個(gè)可變字符串所保存的字符串的長(zhǎng)度。緩沖區(qū)的一個(gè)數(shù)組，數(shù)組的字節(jié)分別保存了不同的字符，可變字符串遵循c字符串以空字符結(jié)尾的慣例，最后一個(gè)字節(jié)則保存了空字符＼0.

4字典dict

4.1字典的設(shè)計(jì)

哈希算法一般用于快速查詢的算法，可以將任意長(zhǎng)度的二進(jìn)制的數(shù)值對(duì)應(yīng)為較為簡(jiǎn)短的固定長(zhǎng)度的二進(jìn)制數(shù)值，這個(gè)二進(jìn)制的值就是哈希值。

簡(jiǎn)單的說(shuō)，哈希算法的哈希函數(shù)可以將任意長(zhǎng)度的輸入經(jīng)過(guò)變化以后得到固定長(zhǎng)度的輸出。哈希函數(shù)的這種單向特征和輸出數(shù)據(jù)長(zhǎng)度固定的特征使得它可以生成消息或者數(shù)據(jù)。當(dāng)要將一個(gè)新的鍵值對(duì)添加到字典里面時(shí)， 程序需要先根據(jù)鍵值對(duì)的鍵計(jì)算出哈希值和索引值， 然后再根據(jù)索引值， 將包含新鍵值對(duì)的哈希表節(jié)點(diǎn)放到哈希表數(shù)組的指定索引上面。

4.2字典的實(shí)現(xiàn)

字典使用哈希表作為底層實(shí)現(xiàn)， 一個(gè)哈希表里面可以有多個(gè)哈希表節(jié)點(diǎn)， 而每個(gè)哈希表節(jié)點(diǎn)就保存了字典中的一個(gè)鍵值對(duì)。

（1）字典所使用哈希表

數(shù)組中的每個(gè)元素都是一個(gè)指向dict.h結(jié)構(gòu)的指針， 每個(gè)字典入口結(jié)構(gòu)保存著一個(gè)鍵值對(duì)。

記錄了哈希表的大小的屬性， 也就是數(shù)組的大小， 在用一個(gè)專門的屬性記錄了哈希表目前已有節(jié)點(diǎn)（鍵值對(duì)）的數(shù)量。

再有一個(gè)表面屬性 ，這個(gè)屬性和哈希值一起決定一個(gè)鍵應(yīng)該被放到數(shù)組的哪個(gè)索引上面。

（2）哈希表的每個(gè)節(jié)點(diǎn)都保存著一個(gè)鍵值對(duì)：

其中一個(gè)哈希表節(jié)點(diǎn)的指針，可以將多個(gè)哈希值相同的鍵值對(duì)連接在一次， 以此來(lái)解決鍵沖突的問(wèn)題。

（3）字典由 dict.h結(jié)構(gòu)表示：

針對(duì)不同類型的鍵值對(duì)， 為創(chuàng)建多態(tài)字典而設(shè)置類型屬性，類型屬性是一個(gè)指向字典類型結(jié)構(gòu)的指針， 每個(gè)字典類型結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對(duì)的函數(shù)。

5壓縮集合zipset

5.1壓縮集合的設(shè)計(jì)

壓縮集合用于保存整數(shù)值得集合抽象數(shù)據(jù)結(jié)構(gòu)，可以保存int型的整數(shù)值，而且可以保證集合中不會(huì)出現(xiàn)重復(fù)元素。當(dāng)一個(gè)集合只包含整數(shù)值元素，并且這個(gè)集合的元素?cái)?shù)量不多的時(shí)候，就可以是使用壓縮集合作為集合鍵的底層結(jié)構(gòu)。

5.1壓縮集合的實(shí)現(xiàn)

在壓縮集合代碼實(shí)現(xiàn)的zipset.c文件中，每個(gè)壓縮集合，長(zhǎng)度屬性記錄整數(shù)集合的包含的元素個(gè)數(shù)也就是數(shù)組的長(zhǎng)度，數(shù)組的類型取決于編碼屬性的值。

6壓縮列表ziplist

6.1壓縮列表的設(shè)計(jì)

壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)， 并且每個(gè)列表項(xiàng)要么就是小整數(shù)值， 要么就是長(zhǎng)度比較短的字符串， 那么就會(huì)使用壓縮列表來(lái)做列表鍵的底層實(shí)現(xiàn)。

6.2壓縮列表的實(shí)現(xiàn)

一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)， 每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。整個(gè)壓縮列表的組成包括記錄整個(gè)壓縮列表占用內(nèi)存字節(jié)數(shù)的屬性；記錄壓縮列表表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)的屬性，通過(guò)這個(gè)偏移量，就可以不用遍歷整個(gè)壓縮列表就可以確定表尾節(jié)點(diǎn)的地址；記錄壓縮列表包含節(jié)點(diǎn)數(shù)量的屬性；以及用于標(biāo)記壓縮列表的末端的屬性。

7 結(jié)束語(yǔ)

內(nèi)存數(shù)據(jù)庫(kù)在軟件系統(tǒng)開(kāi)發(fā)中的應(yīng)用，極大地提高系統(tǒng)運(yùn)行的處理能力，內(nèi)存數(shù)據(jù)庫(kù)，通過(guò)避開(kāi)磁盤(pán)的耗時(shí)操作，內(nèi)存優(yōu)化的索引結(jié)構(gòu)快速的日志和恢復(fù)，高并發(fā)的事務(wù)處理，達(dá)到了高性能的數(shù)據(jù)管理能力，低成本的基礎(chǔ)上大大提高系統(tǒng)的處理能力。大量的數(shù)據(jù)操作通過(guò)內(nèi)存數(shù)據(jù)庫(kù)集中管理，也增強(qiáng)了系統(tǒng)開(kāi)發(fā)中的擴(kuò)展能力。

參考文獻(xiàn)：

[1] 張曉偉.探討分布式內(nèi)存數(shù)據(jù)庫(kù)的設(shè)計(jì)與應(yīng)用[J].硅谷， 2009（03）

[2] 王慧嬪.基于MMDB技術(shù)對(duì)電信計(jì)費(fèi)系統(tǒng)研究與實(shí)現(xiàn)的探討[J].科技資訊， 2009（16）

[3] 王金華，江水，吳嫻，盧瑤，龍剛.輕量級(jí)內(nèi)存數(shù)據(jù)庫(kù)的研究[J].計(jì)算機(jī)工程， 2008（S1）

[4] 王珊，肖艷芹，劉大為，覃雄派.內(nèi)存數(shù)據(jù)庫(kù)關(guān)鍵技術(shù)研究[J].計(jì)算機(jī)應(yīng)用， 2007（10）

[5] 朱勇，張炯，沈軼.內(nèi)存數(shù)據(jù)庫(kù)在移動(dòng)計(jì)費(fèi)系統(tǒng)中的應(yīng)用[J].現(xiàn)代機(jī)械， 2007（05）