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

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

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

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

動態(tài)類型模塊

需求

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

分析

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

設(shè)計

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

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

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

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

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

日志模塊

需求

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

分析

為了降低IO代價，必然要進行定點增量式寫入。因此需要將每一次對表的修改（增刪改）作為一條日志記錄，

設(shè)計

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

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

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

視圖與表抽取模塊

需求

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

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

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

分析

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

設(shè)計

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

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

首先定義視圖類（view類），其需要存儲其所映射到的基本表，和視圖中每個元組在基本表中對應的位置（下標）。

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

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

列/表模塊

需求

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

分析

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

設(shè)計

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

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

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

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

索引模塊

需求

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

分析

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

設(shè)計

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

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

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

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

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

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

需求

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

分析

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

設(shè)計

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

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

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

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

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

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