SG-Database一種輕量、易擴(kuò)展的關(guān)系式數(shù)據(jù)庫(kù)系統(tǒng)。

其主要優(yōu)勢(shì)是，可以簡(jiǎn)單方便的向其中添加新的數(shù)據(jù)類型及對(duì)應(yīng)索引。比如當(dāng)我們想要在數(shù)據(jù)庫(kù)中存儲(chǔ)一些地圖上的點(diǎn)，為了對(duì)其進(jìn)行高效索引，需要建立類似KD-Tree等的索引結(jié)構(gòu)，為了在傳統(tǒng)的SQL數(shù)據(jù)庫(kù)中實(shí)現(xiàn)這種索引，需要對(duì)數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)行performance tuning，編程負(fù)擔(dān)較重。而我們的數(shù)據(jù)庫(kù)系統(tǒng)提供了更加方便易用的擴(kuò)展結(jié)構(gòu)，用戶可以直接繼承數(shù)據(jù)類型基類Basic實(shí)現(xiàn)自己的數(shù)據(jù)類型，并添加對(duì)應(yīng)索引。添加的組件可以無(wú)開(kāi)銷地直接對(duì)接數(shù)據(jù)庫(kù)，簡(jiǎn)單方便的實(shí)現(xiàn)對(duì)數(shù)據(jù)庫(kù)系統(tǒng)功能的拓展。

在此基礎(chǔ)上，我們實(shí)現(xiàn)了傳統(tǒng)關(guān)系式數(shù)據(jù)庫(kù)物理層面大部分功能和優(yōu)化，如變更日志、IO優(yōu)化、熱區(qū)緩存、視圖和表抽取、元組批操作等。在高層，我們放棄使用SQL語(yǔ)言，而是采用javascript語(yǔ)言和邏輯規(guī)則引擎聯(lián)合進(jìn)行對(duì)數(shù)據(jù)操作進(jìn)行描述。使用javascript可以完成許多SQL語(yǔ)言很難編寫(xiě)或完成不了的數(shù)據(jù)操作，而且更符合大部分程序員的直覺(jué)。規(guī)則引擎用于描述WHERE條件，直接與索引模塊對(duì)接，使得用戶編寫(xiě)的索引結(jié)構(gòu)可以直接接入查詢功能當(dāng)中。

由于只用了四天事件，還有一些功能我們沒(méi)有完成。如數(shù)據(jù)操作語(yǔ)言(javascript)與數(shù)據(jù)庫(kù)的對(duì)接、觸發(fā)器（因?yàn)檫@與數(shù)據(jù)庫(kù)查詢語(yǔ)言相關(guān)）、與連接操作/多表查詢有關(guān)的一些支持，以及并發(fā)控制（這十分重要，我們要多花一些時(shí)間進(jìn)行研究設(shè)計(jì)）。

動(dòng)態(tài)類型模塊

需求

數(shù)據(jù)庫(kù)需要存儲(chǔ)不同類型的數(shù)據(jù)。因此數(shù)據(jù)庫(kù)系統(tǒng)需要對(duì)數(shù)據(jù)類型提供支持。并要允許用戶簡(jiǎn)單方便的定義自己的新數(shù)據(jù)類型，無(wú)開(kāi)銷地與數(shù)據(jù)庫(kù)其它模塊實(shí)現(xiàn)自動(dòng)對(duì)接。

分析

不同數(shù)據(jù)類型具有不同數(shù)據(jù)成員，所以必須使用不同的類來(lái)存儲(chǔ)。但列與表的對(duì)象都需要同存同取，不能對(duì)每個(gè)類型都建立一個(gè)對(duì)應(yīng)的列/表類。因此需要引入動(dòng)態(tài)類型特性。

設(shè)計(jì)

我們選擇使用繼承多態(tài)實(shí)現(xiàn)動(dòng)態(tài)類型。首先定義數(shù)據(jù)類型基類（Basic類），其它類型均繼承數(shù)據(jù)類型基類實(shí)現(xiàn)。在列類（col類）中，存儲(chǔ)數(shù)據(jù)的對(duì)象為基類容器（vector），即將所有數(shù)據(jù)對(duì)象都向上轉(zhuǎn)型為基類指針統(tǒng)一存儲(chǔ)。

基類中定義虛函數(shù)getType，這個(gè)函數(shù)返回這個(gè)動(dòng)態(tài)類型對(duì)象的類型。因此每個(gè)子類都需要對(duì)該虛函數(shù)進(jìn)行實(shí)現(xiàn)。這樣在向上轉(zhuǎn)型之后依然可以獲取數(shù)據(jù)的實(shí)際類型，以便在使用時(shí)進(jìn)行逆變。

在col對(duì)象構(gòu)造時(shí)，需要指定類型（因?yàn)殛P(guān)系式數(shù)據(jù)庫(kù)中同一列存儲(chǔ)的數(shù)據(jù)類型一定是相同的），當(dāng)取用其中的數(shù)據(jù)時(shí)，按構(gòu)造時(shí)指定的列類型進(jìn)行轉(zhuǎn)換。添加元素時(shí)也會(huì)進(jìn)行類型檢查，如添加的數(shù)據(jù)類型與列類型不符，將會(huì)拋出異常。

為了方便實(shí)現(xiàn)動(dòng)態(tài)類型的配套操作，實(shí)現(xiàn)typeHelper靜態(tài)空間，提供關(guān)于數(shù)據(jù)對(duì)象拷貝、判等、反序列化等功能。這樣，需要使用這些功能時(shí)直接用基類指針作為參數(shù)調(diào)用函數(shù)即可，不需要手動(dòng)轉(zhuǎn)換再根據(jù)不同類型分別處理。相應(yīng)地，在用戶添加新數(shù)據(jù)類型時(shí)，也要在這些函數(shù)中添加新類型的處理case。

作為例子，我們實(shí)現(xiàn)了整型、浮點(diǎn)、字符串、布爾四種實(shí)值類型。

日志模塊

需求

記錄對(duì)用戶數(shù)據(jù)庫(kù)進(jìn)行的修改（增刪改）操作?；谶@些記錄，可以在合適的時(shí)候?qū)⑦@些修改統(tǒng)一寫(xiě)入硬盤(pán)（修改先立刻在內(nèi)存中實(shí)現(xiàn)，再在合適的時(shí)候統(tǒng)一在硬盤(pán)上的文件實(shí)現(xiàn)），降低IO代價(jià)。

分析

為了降低IO代價(jià)，必然要進(jìn)行定點(diǎn)增量式寫(xiě)入。因此需要將每一次對(duì)表的修改（增刪改）作為一條日志記錄，

設(shè)計(jì)

首先定義日志記錄類（record類），其需要記錄三種對(duì)表的修改模式：插入、刪除和修改（元組）。

三種修改所需的信息不同：插入僅需要記錄插入的元組，不關(guān)心位置（元組是無(wú)序的）；刪除只需要記錄刪除的元組（相對(duì)當(dāng)前表的）位置（下標(biāo)）；修改需要記錄需修改元組的位置（下標(biāo)）和修改內(nèi)容（使用vector記錄，長(zhǎng)度為元組長(zhǎng)度，不修改的條目可以使用占位符占位）。因此，三種不同的修改可以使用三種不同的構(gòu)造函數(shù)，在構(gòu)造函數(shù)中記錄修改類型（增/刪/改），便于在實(shí)現(xiàn)修改時(shí)，通過(guò)修改類型進(jìn)入不同的分支。

將這些修改寫(xiě)入硬盤(pán)時(shí)，按日志隊(duì)列順序從頭到尾實(shí)現(xiàn)修改即可。所有修改都已實(shí)現(xiàn)到硬盤(pán)后，日志隊(duì)列將被清空。

視圖與表抽取模塊

需求

快速的使用一個(gè)表中的部分元組構(gòu)造視圖或復(fù)制一張新表。

視圖是從一個(gè)基本表中導(dǎo)出的虛擬的表。在系統(tǒng)的數(shù)據(jù)字典中僅存放了視圖的定義，不存放視圖對(duì)應(yīng)的數(shù)據(jù)。這些表的數(shù)據(jù)存放在數(shù)據(jù)庫(kù)中。那些用于產(chǎn)生視圖的表叫做該視圖的基表。

視圖看上去非常像數(shù)據(jù)庫(kù)的物理表，對(duì)它的操作同任何其它的表一樣。當(dāng)通過(guò)視圖修改數(shù)據(jù)時(shí)，實(shí)際上是在改變基表中的數(shù)據(jù)；相反地，基表數(shù)據(jù)的改變也會(huì)自動(dòng)反映在由基表產(chǎn)生的視圖中。

分析

這是傳統(tǒng)數(shù)據(jù)庫(kù)的常規(guī)功能。表抽取直接創(chuàng)建新的表和列對(duì)象，將選擇的元素復(fù)制進(jìn)去即可。視圖需要建立一個(gè)對(duì)基本表的映射，這樣才能使得對(duì)視圖的修改通過(guò)映射作用到基本表上，使二者同步。

設(shè)計(jì)

視圖并不是一個(gè)很好的設(shè)計(jì)，因?yàn)楸３謹(jǐn)?shù)據(jù)綁定在很多情況下并不容易做到。但我們?nèi)栽诓粨p害運(yùn)行效率和軟件架構(gòu)的情況下對(duì)其的基本功能進(jìn)行實(shí)現(xiàn)。

我們所支持的是單表視圖，因?yàn)槎啾硪晥D需要連接條件才能保持，而在對(duì)視圖進(jìn)行修改時(shí)，動(dòng)態(tài)正/反向解析連接條件以找到所修改元組在基本表中的位置，是非常低效的。在正常的數(shù)據(jù)庫(kù)使用中也應(yīng)該盡量減少這種操作。因此多表視圖在本數(shù)據(jù)庫(kù)中不做支持。

首先定義視圖類（view類），其需要存儲(chǔ)其所映射到的基本表，和視圖中每個(gè)元組在基本表中對(duì)應(yīng)的位置（下標(biāo)）。

這種存儲(chǔ)方式意味著基本表出現(xiàn)任何改變數(shù)據(jù)下標(biāo)的修改時(shí)，視圖都可能不再可用（訪問(wèn)不到正確的元素）。如果對(duì)基本表和視圖進(jìn)行雙向綁定可以解決這種問(wèn)題，但這會(huì)連帶降低基本表的操作效率，并破壞軟件上下層結(jié)構(gòu)。

可以采取的方法是事件路由，即在一個(gè)上層模塊中記錄所有的“視圖-表”綁定，所有的增刪改操作都必須經(jīng)過(guò)這個(gè)模塊實(shí)際實(shí)施，當(dāng)對(duì)一個(gè)基本表進(jìn)行刪除操作時(shí)，在刪除完成后，這個(gè)操作會(huì)被發(fā)送到這個(gè)基本表所派生的所有視圖中，如果這個(gè)操作對(duì)視圖中元素有影響，那么基本表會(huì)進(jìn)行對(duì)應(yīng)修正。具體來(lái)說(shuō)，如果一個(gè)視圖中的元組在基本表中被刪除，那么視圖也會(huì)刪除該元素，并將其之后元素的映射值全部減1. 如果一個(gè)在基本表中被刪除的元素下標(biāo)落在某個(gè)視圖映射到的區(qū)間內(nèi)，那么對(duì)于視圖的映射表，從它右側(cè)距離最近的的元素開(kāi)始，其后所有元素的映射值全部減1.

列/表模塊

需求

設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)庫(kù)中的表

分析

關(guān)系式數(shù)據(jù)庫(kù)表中的不同列具有不同的特性，如不同類型、不同約束、不同觸發(fā)器等。因此需要用一個(gè)單獨(dú)的結(jié)構(gòu)來(lái)表示。這些結(jié)構(gòu)的對(duì)象再堆疊起來(lái)，就形成了表。

設(shè)計(jì)

定義列類（col類），在構(gòu)造函數(shù)中指定該類的數(shù)據(jù)類型和基本約束。并可以通過(guò)成員函數(shù)添加觸發(fā)器和其它約束（因?yàn)槟壳皵?shù)據(jù)查詢語(yǔ)言尚未與數(shù)據(jù)庫(kù)系統(tǒng)完成對(duì)接，觸發(fā)器和約束暫時(shí)不被支持）。當(dāng)向列中添加數(shù)據(jù)時(shí)，會(huì)自動(dòng)檢查添加的數(shù)據(jù)類型是否與列的數(shù)據(jù)類型相同，如果不同將拋出異常。

定義表類（table類），表類需對(duì)列、索引和日志均進(jìn)行支持。表中的所有列在構(gòu)造時(shí)作為構(gòu)造函數(shù)參數(shù)傳入，轉(zhuǎn)移所有權(quán)到表對(duì)象，其后自動(dòng)對(duì)所有列建立索引（默認(rèn)為遍歷索引，即遍歷查詢），用戶可以自行對(duì)某一列構(gòu)造其它索引，并通過(guò)替換索引的成員函數(shù)替換掉原先的索引。日志記錄的功能掛載在表類的增/刪/改方法中，當(dāng)操作完成后，自動(dòng)創(chuàng)建日志記錄追加到日志中。具體參照“日志模塊”章節(jié)。

對(duì)于增/刪/改操作，從表的層次講，其操作的單元是元組。在函數(shù)內(nèi)部，會(huì)將這些對(duì)元組的操作轉(zhuǎn)換為對(duì)對(duì)應(yīng)列的操作，并調(diào)用列的增/刪/改函數(shù)，進(jìn)行實(shí)際實(shí)施。

另外，表類還需支持查詢功能。這里的查詢指的是根據(jù)條件對(duì)表中元素進(jìn)行篩選，即“單表查詢”。多表查詢通過(guò)單表查詢結(jié)果進(jìn)行表提取，再進(jìn)行多次查詢即可完成，之后我們會(huì)對(duì)這一功能進(jìn)行進(jìn)一步封裝。表示條件需要使用邏輯規(guī)則引擎中的規(guī)則表達(dá)式（ruleExp）對(duì)象，每個(gè)對(duì)象表達(dá)對(duì)一列數(shù)據(jù)的條件，查詢過(guò)程需要傳入對(duì)所有列的條件（無(wú)條件的列傳nullptr），然后對(duì)每一列，依次用該列對(duì)應(yīng)條件調(diào)用該列索引進(jìn)行查詢，將最后的結(jié)果取交集。

索引模塊

需求

根據(jù)不同數(shù)據(jù)類型、不同約束的類產(chǎn)生的不同特點(diǎn)。數(shù)據(jù)庫(kù)需要各種不同的索引加速查詢。因此數(shù)據(jù)庫(kù)系統(tǒng)需要對(duì)索引提供支持。并要允許用戶簡(jiǎn)單方便的定義自己的新索引結(jié)構(gòu)，無(wú)開(kāi)銷地與數(shù)據(jù)庫(kù)其它模塊實(shí)現(xiàn)自動(dòng)對(duì)接。

分析

不同索引有著不同的數(shù)據(jù)結(jié)構(gòu)，如B樹(shù)與二叉查找樹(shù)一定是兩個(gè)不同的類型存儲(chǔ)。所以不同的索引也必須使用不同的類來(lái)存儲(chǔ)（將索引使用的實(shí)際數(shù)據(jù)結(jié)構(gòu)作為索引類的成員）。但列與表的對(duì)象都需要同存同取，不能對(duì)每個(gè)類型都建立一個(gè)對(duì)應(yīng)的列/表類。因此仍需要使用繼承多態(tài)。

設(shè)計(jì)

首先定義索引基類（index類），其它索引均繼承基類實(shí)現(xiàn)。在表類（table類）中，存儲(chǔ)索引的對(duì)象為基類容器（vector），即將所有索引對(duì)象都向上轉(zhuǎn)型為基類指針統(tǒng)一存儲(chǔ)。

在本數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)中，所謂“索引”不一定要求有獨(dú)立的查找數(shù)據(jù)結(jié)構(gòu)（如B樹(shù)等）。因?yàn)槊恳淮尾檎揖鶗?huì)調(diào)用索引對(duì)象進(jìn)行，所以即使是順序遍歷查找，也是一種“索引”。但如果是具有獨(dú)立查找數(shù)據(jù)結(jié)構(gòu)的索引，當(dāng)數(shù)據(jù)改變（進(jìn)行增刪改）時(shí)，其對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)需要更新，而像順序查找這類“索引”，就不需要更新。因此有必要對(duì)二者進(jìn)行區(qū)分。所以在基類中，設(shè)置了一個(gè)bool型flag，標(biāo)記該索引類是否需要在每次進(jìn)行增刪改時(shí)同步對(duì)其進(jìn)行更新。如果flag為true，則在表對(duì)象的增/刪/改方法被調(diào)用時(shí)，也會(huì)自動(dòng)調(diào)用索引的增/刪/改虛函數(shù)，使得二者同步（因此這種情況下這三個(gè)虛函數(shù)必須有效實(shí)現(xiàn)）。而如果flag為false，索引類中的增/刪/改虛函數(shù)就不會(huì)被調(diào)用，保持基類的“調(diào)用即拋出異常”實(shí)現(xiàn)即可。

用戶可以繼承索引基類創(chuàng)建自己的索引。如果用戶的索引具有獨(dú)立的查找數(shù)據(jù)結(jié)構(gòu)，那么需要在構(gòu)造函數(shù)中建立這個(gè)數(shù)據(jù)結(jié)構(gòu)、置flag為true，并實(shí)現(xiàn)維護(hù)該結(jié)構(gòu)的增/刪/改虛函數(shù)。無(wú)論是否具有獨(dú)立查找結(jié)構(gòu)，必須實(shí)現(xiàn)查找虛函數(shù)，該函數(shù)傳入一個(gè)條件（由規(guī)則表達(dá)式對(duì)象表示），返回查找結(jié)果。

對(duì)于傳入的規(guī)則條件，查找函數(shù)可能有必要進(jìn)行一些解釋和轉(zhuǎn)化，如NOT-GART（NOT為根節(jié)點(diǎn)，GART為其子節(jié)點(diǎn)）代表小于等于，AND-GART/EQU（AND的兩個(gè)子節(jié)點(diǎn)為GART和EQU）代表大于等于等。有許多表達(dá)方式是等價(jià)的，如果一些邏輯條件對(duì)應(yīng)著查找算法的某條分支，那么就有必要從傳入的規(guī)則表達(dá)式中確定用戶到底描述的是哪種條件——如果是單層的表達(dá)式，這很簡(jiǎn)單。但如果是上文所說(shuō)的嵌套表達(dá)式，就相對(duì)困難（之后我們會(huì)對(duì)表達(dá)式化簡(jiǎn)提供一些封裝）。如果對(duì)復(fù)雜的規(guī)則不想進(jìn)行化簡(jiǎn)（要求用戶必須傳入簡(jiǎn)單的），或者這個(gè)索引根本不支持某種條件，那么可以在檢測(cè)出這種情況時(shí)拋出“index does not support this exp”異常。如果查找算法不依賴規(guī)則進(jìn)行路徑選擇，只需要代入數(shù)據(jù)判斷真值，那么可以直接對(duì)規(guī)則對(duì)象調(diào)用eval函數(shù)，傳入你要代入的數(shù)據(jù)即可。

作為例子，我們實(shí)現(xiàn)了遍歷和B+樹(shù)兩種索引。前者針對(duì)任意列，后者只針對(duì)唯一性約束的數(shù)值（Int/Float）列。

邏輯規(guī)則引擎模塊

需求

設(shè)計(jì)邏輯規(guī)則引擎用于描述數(shù)據(jù)查找（篩選）規(guī)則。

分析

本數(shù)據(jù)庫(kù)系統(tǒng)不使用SQL作為查詢語(yǔ)言，對(duì)數(shù)據(jù)的操作由javascript腳本結(jié)合操作庫(kù)來(lái)完成。但對(duì)于數(shù)據(jù)的查找（篩選）規(guī)則，無(wú)法直接使用javascript程序描述。因?yàn)椴煌臈l件可能對(duì)應(yīng)不同查找算法（索引）中的不同執(zhí)行路徑，這個(gè)規(guī)則的表示起的是一個(gè)指示作用，表達(dá)“想要什么”而不是“要怎么做”（具體怎么做由查找算法實(shí)現(xiàn)）。所以必須使用一個(gè)可拆分、可組合的數(shù)據(jù)結(jié)構(gòu)，用戶可以對(duì)其進(jìn)行組合，表達(dá)自己想要的查詢；查找算法對(duì)其進(jìn)行拆分，找到對(duì)應(yīng)的算法執(zhí)行路徑。

設(shè)計(jì)

我們采用類似表達(dá)式樹(shù)的結(jié)構(gòu)。每個(gè)規(guī)則表達(dá)式對(duì)象有兩個(gè)子節(jié)點(diǎn)。因?yàn)樵趩伪聿樵冎?，條件都是諸如AGE>18之類，一側(cè)是一個(gè)常量，另一側(cè)用列中的數(shù)據(jù)替代。因此在構(gòu)造表達(dá)式對(duì)象時(shí)，常量子節(jié)點(diǎn)需要被指定。常量子節(jié)點(diǎn)有兩種類型可選，一是像上文所說(shuō)為一個(gè)實(shí)際的數(shù)據(jù)對(duì)象，也可以依然為一個(gè)表達(dá)式對(duì)象，以實(shí)現(xiàn)表達(dá)式的嵌套。一些運(yùn)算（如NOT）只需要一個(gè)操作數(shù)，就用常量子節(jié)點(diǎn)作為這個(gè)操作數(shù)。

在進(jìn)行多表查詢時(shí)，常量子節(jié)點(diǎn)需要依次被表2中的數(shù)據(jù)替代。所以我們提供了一個(gè)成員函數(shù)用于修改這個(gè)表達(dá)式對(duì)象的常量子節(jié)點(diǎn)。

一些時(shí)候，查找算法并不僅僅要知道表達(dá)式對(duì)象所要表達(dá)的條件，還需要將數(shù)據(jù)代入表達(dá)式進(jìn)行實(shí)際求值。因此需要提供eval方法，eval傳入一個(gè)數(shù)據(jù)作為變量子節(jié)點(diǎn)的取值（查詢（篩選）問(wèn)題中，所有子樹(shù)變量子節(jié)點(diǎn)的取值都是相同的，如對(duì)AGE列的篩選條件AGE>18 AND AGE<60）。其實(shí)現(xiàn)就是遞歸求值。

只要運(yùn)算的結(jié)果是邏輯值，就被稱為邏輯操作。因此規(guī)則引擎支持的運(yùn)算不應(yīng)當(dāng)僅限于AND、OR、NOT等，也應(yīng)允許用戶拓展。在我們的設(shè)計(jì)中，表達(dá)式基類不限定操作數(shù)的數(shù)據(jù)類型，所以僅支持EQU（判斷相等）運(yùn)算（因?yàn)檫@個(gè)運(yùn)算也不要求操作數(shù)類型）。其它類型特化的運(yùn)算都由子類進(jìn)行實(shí)現(xiàn)（因此也要求eval為虛函數(shù)）。

我們注意到，手動(dòng)構(gòu)造表達(dá)式樹(shù)結(jié)構(gòu)比較繁瑣。因此之后會(huì)實(shí)現(xiàn)javascript邏輯表達(dá)式（字符串）向表達(dá)式樹(shù)的轉(zhuǎn)換模塊。

作為例子，我們實(shí)現(xiàn)了數(shù)值型的邏輯表達(dá)式類用于進(jìn)行<、>運(yùn)算；布爾型的邏輯表達(dá)式類用于進(jìn)行AND、OR、NOT運(yùn)算。