自己動手寫數據庫: 實現基於靜態哈希的索引
數據庫設計中有一項至關重要的技術難點，那就是給定特定條件進行查詢時，我們需要保證速度儘可能快。假設我們有一個 STUDENT 表，表中包含學生名字，年齡，專業等字段，當我們要查詢給定年齡數值的記錄，如果我們能把所有記錄以年齡字段排序，那麼通過二分查找，我們就能快速定位滿足條件的記錄。如果表中包含 N=1,000,000 條記錄，通過二分查找就能通過大概 logN = 20 次即可，但是要遍歷所有記錄來找，就得查詢一百萬次。
但根據某個字段來排序記錄，當查詢以另外字段查詢時就無法得到相應加速。因此如何通過合適算法，讓數據進行相應組織，使得查詢根據不同字段進行時都能得到相應加速是數據庫設計的核心難題。
在不改變表結構的情況下，要能根據不同字段加快查詢速度，就需要索引制度。索引本質是一個文件，其中的數據是對給定表的記錄分佈進行描述和說明。索引文件中的數據以一條條記錄的方式存在，一條記錄包含兩個字段，一個字段叫 datarid，它是一個指針，指向某條特定數據所在的位置，另一個字段叫 dataval, 它可以是建立索引的字段的值，如果我們要想針對兩個字段 age, name 進行索引，那麼索引文件鐘就包含兩種記錄，一種記錄的 dataval 對應 age 的值，另一種記錄的 dataval 存儲 name 的值，然後記錄根據 dataval 的值排序，於是我們要根據 age 查詢時，我們先通過折半查找在第一種記錄鍾查詢到 VALUE 爲給定查詢值的記錄，然後通過 datarid 字段獲取給定記錄在硬盤的位置，另外需要注意的是，索引信息也是存儲在文件中，獲取索引信息也需要訪問磁盤，因此我們需要使用好的所有算法儘可能減少在查詢索引信息時對磁盤區塊的讀取。
使用索引文件創建索引數據來記錄每條記錄的位置還有一個問題，那就是記錄會刪除和修改，一旦相關記錄刪除和修改後，索引中的數據就需要進行相應變動，這裏我們就需要 B 樹，B + 樹等相關算法的支持。
還需要注意的是，一旦能快速定位所需記錄的位置，我們就能定位記錄所在的區塊從而大大減少對硬盤的訪問次數。但也有例外的情況，當建立索引的字段取值重複性很小時，索引的效率就好，如果索引字段取值的重複性很高，那麼效率反而有可能會降低。
我們把索引建立的基本流程展示如下：
1，當解釋執行索引建立的 SQL 語句時，例如 create majoridIDX on student (majorid)，
create nameIDX on student (name)， 啓動索引建立流程
2，索引流程首先創建專門存儲索引信息的表 idxcat, 其字段爲 indexname, tablename, fildname，這些字段分別用於存儲索引的名稱，建立索引的表名和字段名稱。
3，選擇索引算法，這裏我們先使用前面說的哈希索引。我們使用一個哈希函數 hash，假設他能將輸入的數據哈希到 0-1000 這範圍內的整數值， 假設字段 majorid 的取值 20 和 100 經過該函數後輸出結果相同爲 39，那麼代碼將創建一個名爲 majoroid#39 的記錄表來存儲這兩條記錄的訪問信息 (blockid 和 offset)，上圖，該表的字段爲 dataval，block, id 分別用於存儲記錄對應索引字段的值，記錄所在的 blockid 和 offset 也就是偏移。
在上面例子中由於 majorid 爲 20 和 100 的記錄都哈希到數值 39，因此他們這兩條記錄的存儲信息都存儲在表 majorid#39 這個表中，記錄中字段爲 name=”jim” 的記錄，由於”jim” 哈希的結果爲 69，因此該記錄的存儲信息放置在表 name#69 中。
哈希索引的效率取決於所尋求哈希函數的取值範圍，假設函數哈希結果取值範圍爲 0-N，那麼對於一個包含 M 條記錄的的表，他對應記錄的存儲信息將放置在 M/N 個哈希記錄表中。哈希索引法在理論上能將記錄的查詢時間從 M 優化到 M/N。
4，在執行 select 語句進行記錄查詢時，首先在索引表 idxcat 中查詢給定表和對應字段是否已經建立了索引，如果建立了，那麼直接從對應的查詢記錄表中獲得記錄的存儲信息，然後直接從硬盤讀取記錄數據。
我們看對應代碼實現，索引管理器的實現依然放在 metadata_manager 路徑下，創建一個名爲 index_manager.go 的文件，增加代碼如下：
package metadata_manager
//索引管理器需要使用到後面纔講到的SQL查詢和索引算法知識，所以先放一放
import (
"query"
rm "record_manager"
"tx"
)
type IndexManager struct {
layout *rm.Layout
tblMgr *TableManager
statMgr *StatManager
}
func NewIndexManager(isNew bool, tblMgr *TableManager, statMgr *StatManager, tx *tx.Transation) *IndexManager {
if isNew {
//索引元數據表包含三個字段，索引名，對應的表名，被索引的字段名
sch := rm.NewSchema()
sch.AddStringField("indexname", MAX_NAME)
sch.AddStringField("tablename", MAX_NAME)
sch.AddStringField("fieldname", MAX_NAME)
tblMgr.CreateTable("idxcat", sch, tx)
}
idxMgr := &IndexManager{
tblMgr: tblMgr,
statMgr: statMgr,
layout: tblMgr.GetLayout("idxcat", tx),
}
return idxMgr
}
func (i *IndexManager) CreateIndex(idxName string, tblName string, fldName string, tx *tx.Transation) {
//創建索引時就爲其在idxcat索引元數據表中加入一條記錄
ts := query.NewTableScan(tx, "idxcat", i.layout)
ts.BeforeFirst()
ts.Insert()
ts.SetString("indexname", idxName)
ts.SetString("tablename", tblName)
ts.SetString("fieldname", fldName)
ts.Close()
}
func (i *IndexManager) GetIndexInfo(tblName string, tx *tx.Transation) map[string]*IndexInfo {
result := make(map[string]*IndexInfo)
ts := query.NewTableScan(tx, "idxcat", i.layout)
ts.BeforeFirst()
for ts.Next() {
if ts.GetString("tablename") == tblName {
idxName := ts.GetString("indexname")
fldName := ts.GetString("fieldname")
tblLayout := i.tblMgr.GetLayout(tblName, tx)
tblSi := i.statMgr.GetStatInfo(tblName, tblLayout, tx)
schema, ok := (tblLayout.Schema()).(*rm.Schema)
if ok != true {
panic("convert schema interface error")
}
ii := NewIndexInfo(idxName, fldName, schema, tx, tblSi)
result[fldName] = ii
}
}
ts.Close()
return result
}
IndexManager 的作用是創建索引記錄表 idxcat，該表記錄有哪些索引建立在哪些表上，idxcat 表包含三個字段，分別是 indexname, tablename 和 fildname。由於爲了支持能夠靈活的選取不同的索引算法，在代碼上我們增加了一箇中間件叫 IndexInfo，由它來負責創建所需要的索引算法對象。由於我們可能對不同的字段採取不同的索引算法，因此 GetIndexInfo 返回了一個 map 對象，該字典的 key 對應索引字段的名稱，value 對應 IndexInfo 對象，我們看看後者的實現：
package metadata_manager
import (
rm "record_manager"
"tx"
)
type IndexInfo struct {
idxName string
fldName string
tblSchema *rm.Schema
tx *tx.Transation
idxLayout *rm.Layout
si *StatInfo
}
func NewIndexInfo(idxName string, fldName string, tblSchema *rm.Schema,
tx *tx.Transation, si *StatInfo) *IndexInfo {
idxInfo := &IndexInfo{
idxName: idxName,
fldName: fldName,
tx: tx,
tblSchema: tblSchema,
si: si,
idxLayout: nil,
}
idxInfo.idxLayout = idxInfo.CreateIdxLayout()
return idxInfo
}
func (i *IndexInfo) Open() Index {
//在這裏 構建不同的哈希算法對象 s
return NewHashIndex(i.tx, i.idxName, i.idxLayout)
}
func (i *IndexInfo) BlocksAccessed() int {
rpb := int(i.tx.BlockSize()) / i.idxLayout.SlotSize()
numBlocks := i.si.RecordsOutput() / rpb
return HashIndexSearchCost(numBlocks, rpb)
}
func (i *IndexInfo) RecordsOutput() int {
return i.si.RecordsOutput() / i.si.DistinctValues(i.fldName)
}
func (i *IndexInfo) DistinctValues(fldName string) int {
if i.fldName == fldName {
return 1
}
return i.si.DistinctValues(fldName)
}
func (i *IndexInfo) CreateIdxLayout() *rm.Layout {
sch := rm.NewSchema()
sch.AddIntField("block")
sch.AddIntField("id")
if i.tblSchema.Type(i.fldName) == rm.INTEGER {
sch.AddIntField("dataval")
} else {
fldLen := i.tblSchema.Length(i.fldName)
sch.AddStringField("dataval", fldLen)
}
return rm.NewLayoutWithSchema(sch)
}
我們注意看 IndexInfo 的實現中有一個接口例如 DistincValues 等跟我們以前實現的 StateInfo 一樣，他負責返回當前索引算法效率的相關信息，對於哈希索引而言，很多效率指標都是固定的，搜索的效率就是 M/N，其中 M 是表中記錄的條數，N 就是索引函數取值的範圍。下面我們看哈希索引的實現，新建 hash_index.go 文件，輸入代碼如下：
package metadata_manager
import (
"fmt"
"query"
rm "record_manager"
"tx"
)
const (
NUM_BUCKETS = 100
)
type HashIndex struct {
tx *tx.Transation
idxName string
layout *rm.Layout
searchKey *query.Constant
ts *query.TableScan
}
func NewHashIndex(tx *tx.Transation, idxName string, layout *rm.Layout) *HashIndex {
return &HashIndex{
tx: tx,
idxName: idxName,
layout: layout,
ts: nil,
}
}
func (h *HashIndex) BeforeFirst(searchKey *query.Constant) {
h.Close()
h.searchKey = searchKey
bucket := searchKey.HashCode() % NUM_BUCKETS
//構造索引記錄對應的表名稱
tblName := fmt.Sprintf("%s#%d", h.idxName, bucket)
h.ts = query.NewTableScan(h.tx, tblName, h.layout)
}
func (h *HashIndex) Next() bool {
for h.ts.Next() {
if h.ts.GetVal("dataval").Equals(h.searchKey) {
return true
}
}
return false
}
func (h *HashIndex) GetDataRID() *rm.RID {
//返回記錄所在的區塊信息
blkNum := h.ts.GetInt("block")
id := h.ts.GetInt("id")
return rm.NewRID(blkNum, id)
}
func (h *HashIndex) Insert(val *query.Constant, rid *rm.RID) {
h.BeforeFirst(val)
h.ts.Insert()
h.ts.SetInt("block", rid.BlockNumber())
h.ts.SetInt("id", rid.Slot())
h.ts.SetVal("dataval", val)
}
func (h *HashIndex) Delete(val *query.Constant, rid *rm.RID) {
h.BeforeFirst(val)
for h.Next() {
if h.GetDataRID().Equals(rid) {
h.ts.Delete()
return
}
}
}
func (h *HashIndex) Close() {
if h.ts != nil {
h.ts.Close()
}
}
func HashIndexSearchCost(numBlocks int, rpb int) int {
return numBlocks / NUM_BUCKETS
}
HashIndex 對象會根據索引字段的名稱和哈希計算結果來新建一個存儲被索引記錄區塊信息的表，如果索引字段爲 majorid，記錄對應 majorid 字段的取值爲 20，哈希計算結果爲 39，他就會創建名爲 majorid#39 的表，表中包含三個字段分別是 dataval, block, id，dataval 存儲哈希字段的取值，block 對應記錄所在的區塊號，id 對應偏移，當我們想要讀取給定記錄時，只要從該表中拿出 block 和 id 的值，就能直接讀取磁盤上給定位置的數據。
在 MetaDataManager 的實現中，我們需要在他的實現中增加索引管理器的創建，對應代碼如下：
package metadata_manager
import (
"query"
rm "record_manager"
"tx"
)
type MetaDataManager struct {
tblMgr *TableManager
viewMgr *ViewManager
statMgr *StatManager
constant *query.Constant
//索引管理器以後再處理
idxMgr *IndexManager
}
func NewMetaDataManager(isNew bool, tx *tx.Transation) *MetaDataManager {
metaDataMgr := &MetaDataManager{
tblMgr: NewTableManager(isNew, tx),
constant: nil,
}
metaDataMgr.viewMgr = NewViewManager(isNew, metaDataMgr.tblMgr, tx)
metaDataMgr.statMgr = NewStatManager(metaDataMgr.tblMgr, tx)
metaDataMgr.idxMgr = NewIndexManager(isNew, metaDataMgr.tblMgr,
metaDataMgr.statMgr, tx)
return metaDataMgr
}
func (m *MetaDataManager) CreateTable(tblName string, sch *rm.Schema, tx *tx.Transation) {
m.tblMgr.CreateTable(tblName, sch, tx)
}
func (m *MetaDataManager) CreateView(viewName string, viewDef string, tx *tx.Transation) {
m.viewMgr.CreateView(viewName, viewDef, tx)
}
func (m *MetaDataManager) GetLayout(tblName string, tx *tx.Transation) *rm.Layout {
return m.tblMgr.GetLayout(tblName, tx)
}
func (m *MetaDataManager) GetViewDef(viewName string, tx *tx.Transation) string {
return m.viewMgr.GetViewDef(viewName, tx)
}
func (m *MetaDataManager) GetStatInfo(tblName string, layout *rm.Layout, tx *tx.Transation) *StatInfo {
return m.statMgr.GetStatInfo(tblName, layout, tx)
}
func (m *MetaDataManager) CreateIndex(idxName string, tblName string, fldName string, tx *tx.Transation) {
m.idxMgr.CreateIndex(idxName, tblName, fldName, tx)
}
func (m *MetaDataManager) GetIndexInfo(tblName string, tx *tx.Transation) map[string]*IndexInfo {
return m.idxMgr.GetIndexInfo(tblName, tx)
}
最後我們在 main.go 中將上面代碼調用起來看看運行效果：
package main
import (
bmg "buffer_manager"
fm "file_manager"
"fmt"
lm "log_manager"
metadata_manager "metadata_management"
"parser"
"planner"
"query"
"tx"
)
func PrintStudentTable(tx *tx.Transation, mdm *metadata_manager.MetaDataManager) {
queryStr := "select name, majorid, gradyear from STUDENT"
p := parser.NewSQLParser(queryStr)
queryData := p.Query()
test_planner := planner.CreateBasicQueryPlanner(mdm)
test_plan := test_planner.CreatePlan(queryData, tx)
test_interface := (test_plan.Open())
test_scan, _ := test_interface.(query.Scan)
for test_scan.Next() {
fmt.Printf("name: %s, majorid: %d, gradyear: %d\n",
test_scan.GetString("name"), test_scan.GetInt("majorid"),
test_scan.GetInt("gradyear"))
}
}
func TestIndex() {
file_manager, _ := fm.NewFileManager("student", 4096)
log_manager, _ := lm.NewLogManager(file_manager, "logfile.log")
buffer_manager := bmg.NewBufferManager(file_manager, log_manager, 3)
tx := tx.NewTransation(file_manager, log_manager, buffer_manager)
fmt.Printf("file manager is new: %v\n", file_manager.IsNew())
mdm := metadata_manager.NewMetaDataManager(file_manager.IsNew(), tx)
//創建 student 表，並插入一些記錄
updatePlanner := planner.NewBasicUpdatePlanner(mdm)
createTableSql := "create table STUDENT (name varchar(16), majorid int, gradyear int)"
p := parser.NewSQLParser(createTableSql)
tableData := p.UpdateCmd().(*parser.CreateTableData)
updatePlanner.ExecuteCreateTable(tableData, tx)
insertSQL := "insert into STUDENT (name, majorid, gradyear) values(\"tylor\", 30, 2020)"
p = parser.NewSQLParser(insertSQL)
insertData := p.UpdateCmd().(*parser.InsertData)
updatePlanner.ExecuteInsert(insertData, tx)
insertSQL = "insert into STUDENT (name, majorid, gradyear) values(\"tom\", 35, 2023)"
p = parser.NewSQLParser(insertSQL)
insertData = p.UpdateCmd().(*parser.InsertData)
updatePlanner.ExecuteInsert(insertData, tx)
fmt.Println("table after insert:")
PrintStudentTable(tx, mdm)
//在 student 表的 majorid 字段建立索引
mdm.CreateIndex("majoridIdx", "STUDENT", "majorid", tx)
//查詢建立在 student 表上的索引並根據索引輸出對應的記錄信息
studetPlan := planner.NewTablePlan(tx, "STUDENT", mdm)
updateScan := studetPlan.Open().(*query.TableScan)
//先獲取每個字段對應的索引對象,這裏我們只有 majorid 建立了索引對象
indexes := mdm.GetIndexInfo("STUDENT", tx)
//獲取 majorid 對應的索引對象
majoridIdxInfo := indexes["majorid"]
//將改rid 加入到索引表
majorIdx := majoridIdxInfo.Open()
updateScan.BeforeFirst()
for updateScan.Next() {
//返回當前記錄的 rid
dataRID := updateScan.GetRid()
dataVal := updateScan.GetVal("majorid")
majorIdx.Insert(dataVal, dataRID)
}
//通過索引表獲得給定字段內容的記錄
majorid := 35
majorIdx.BeforeFirst(query.NewConstantWithInt(&majorid))
for majorIdx.Next() {
datarid := majorIdx.GetDataRID()
updateScan.MoveToRid(datarid)
fmt.Printf("student name :%s, id: %d\n", updateScan.GetScan().GetString("name"),
updateScan.GetScan().GetInt("majorid"))
}
majorIdx.Close()
updateScan.GetScan().Close()
tx.Commit()
}
func main() {
TestIndex()
}
在代碼中我們先創建 STUDENT 表，插入兩條記錄，然後創建一個名爲 majoridIdx 的索引，該索引對應的字段就是 majorid，然後代碼通過 IndexInfo 創建 HashIndex 對象，接着代碼遍歷 STUDENT 表中的每條記錄，獲取這些記錄對應的 blockid 和偏移 offset，HashIndex 將對應記錄的字段值進行哈希後創建對應的索引記錄表，然後將每條記錄的 block id 和 offset 插入記錄表中。
最後代碼遍歷創建的索引記錄表，從中找到索引值爲 35 的記錄，然後取出記錄對應的 block id 和 offset，通過這兩個信息直接從磁盤上將記錄信息讀取並顯示出來，上面代碼運行後結果如下：
file manager is new: true
table after insert:
name: tylor, majorid: 30, gradyear: 2020
name: tom, majorid: 35, gradyear: 2023
student name :tom, id: 35
transation 1 committed從輸出我們可以看到，代碼能直接通過索引記錄表的記錄信息直接查找想要的記錄，不用向我們前面做的那樣，在查詢想要的記錄時，將整個表的每條記錄都搜索一遍，由此我們就能有效的提升查詢效率。代碼下載：
https://github.com/wycl16514/database_hashindex
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Y7kI66xg8NqKOQFrk7FuQA