于鍵值（KV）的表

基于鍵值（KV）的表

在這里插入圖片描述

將行編碼為鍵值（KVs）

索引查詢：點查詢和范圍查詢

在關系型數據庫中，數據被建模為由行和列組成的二維表。用戶通過SQL表達他們的意圖，而數據庫則神奇地提供結果。不那么神奇的是，雖然數據庫可以執行任意查詢，并非所有查詢在OLTP工作負載中都是實際可行的（高效且可擴展），并且OLTP總是要求用戶通過適當的模式和索引設計來控制查詢的執行方式。

一個索引查詢的執行歸結為兩個操作：

  1. 點查詢：根據給定的鍵查找一行。
  2. 范圍查詢：根據一個范圍查找多行；以排序順序迭代結果。

這就是為什么B+樹和LSM樹被認為是適用的，而哈希表則不然。

主鍵作為“鍵”

首先考慮點查詢。要找到一行，必須有一種方法唯一標識該行，這就是主鍵，它是列的一個子集。

create table t1 (k1 string,k2 int,v1 string,v2 string,primary key (k1, k2)
);
表名鍵值
t1k1, k2v1, v2
作為單獨表的輔助索引

除了主鍵外，表可以通過多種方式進行索引。這是通過額外的間接層解決的：輔助索引。

create table t1 (k1 string,k2 int,v1 string,v2 string,primary key (k1, k2),index idx1 (v1),index idx2 (v2, v1)
);

邏輯上，每個索引就像一個單獨的表：

create table idx1 (-- 索引鍵 (v1)v1 string,-- 主鍵 (k1, k2)k1 string,k2 int
);create table idx2 (-- 索引鍵 (v2, v1)v2 string,v1 string,-- 主鍵 (k1, k2)k1 string,k2 int
);

為找到唯一的主鍵增加了額外的鍵。

表名鍵值
t1k1, k2v1, v2
idx1v1k1, k2
idx2v2, v1k1, k2

主鍵也是一種索引，但它具有唯一約束。

替代方案：自動生成的行ID

一些數據庫使用自動生成的ID作為“真正的”主鍵，而不是用戶選擇的主鍵。在這種情況下，主鍵和次鍵之間沒有區別；用戶主鍵也是一個間接層。

表名鍵值
t1IDk1, k2, v1, v2
primary keyk1, k2ID
idx1v1ID
idx2v2, v1ID

優點在于自動生成的ID可以是一個小的、固定寬度的整數，而用戶主鍵則可以任意長。這意味著…

  • 對于ID鍵，內部節點可以存儲更多的鍵（更短的樹）。
  • 輔助索引更小，因為它們不會重復用戶主鍵。

數據庫模式

表前綴

一個數據庫可以包含多個表和索引。我們將為鍵添加一個自動生成的前綴，以便它們能夠共享單個B+樹。這樣做比維護多個樹的工作量要少。

以下是將給定內容轉換成表格的形式：

keyvalue
table1prefix1 + columns…columns…
table2prefix2 + columns…columns…
index1prefix3 + columns…columns…

這個表格展示了不同表和索引的鍵值對結構，其中 key 列表示表或索引的名稱，而 value 列則描述了對應的前綴和列信息。

前綴是一個32位自增整數，你也可以使用表名代替，但缺點是它可能會非常長。

數據類型

關系型數據庫優于鍵值存儲的一個優點是支持更多的數據類型。為了反映這一點，我們將支持兩種數據類型：字符串（string）和整數（integer）。

  • 數據類型：與僅能存儲簡單鍵值對的鍵值存儲不同，關系型數據庫支持更豐富的數據類型。這里提到的支持兩種基本的數據類型——字符串和整數，意味著數據庫可以存儲文本信息和數值信息，從而提供了更高的靈活性和功能。例如，在創建表時，你可以指定列的數據類型為字符串或整數，這有助于確保數據的一致性和正確性。

常量定義

const (TYPE_BYTES = 1 // 字符串（任意字節）TYPE_INT64 = 2 // 整數；64位有符號
)
  • TYPE_BYTES 表示字符串類型，可以存儲任意字節。
  • TYPE_INT64 表示整數類型，使用64位有符號整數。

單元格值結構

// 表單元格
type Value struct {Type uint32 // 類型標記的聯合體I64  int64  // 整數值Str  []byte // 字符串值
}
  • Value 是一個帶有類型標記的聯合體，具體類型由 Type 字段決定。
    • 如果 Type == TYPE_BYTES，則使用 Str 字段存儲字符串數據。
    • 如果 Type == TYPE_INT64，則使用 I64 字段存儲整數數據。

表記錄結構

// 表行
type Record struct {Cols []string // 列名Vals []Value  // 列值
}
  • Record 表示一行數據，包含列名和對應的列值。
  • 列名和列值通過數組的形式一一對應。
添加字符串值的方法
func (rec *Record) AddStr(col string, val []byte) *Record {rec.Cols = append(rec.Cols, col)rec.Vals = append(rec.Vals, Value{Type: TYPE_BYTES, Str: val})return rec
}
  • AddStr 方法用于向記錄中添加一個字符串類型的列值。
  • 參數：
    • col：列名。
    • val：列值（字符串）。
  • 返回值：更新后的記錄對象。
添加整數值的方法
func (rec *Record) AddInt64(col string, val int64) *Record
  • AddInt64 方法用于向記錄中添加一個整數類型的列值。
  • 參數：
    • col：列名。
    • val：列值（整數）。
  • 返回值：更新后的記錄對象。
獲取列值的方法
func (rec *Record) Get(col string) *Value
  • Get 方法根據列名返回對應的列值。
  • 參數：
    • col：列名。
  • 返回值：指向列值的指針。

表模式定義

type TableDef struct {// 用戶定義的部分Name   string   // 表名Types  []uint32 // 列類型Cols   []string // 列名PKeys  int      // 主鍵列的數量// 前 `PKeys` 列是主鍵// 不同表的自動分配的 B 樹鍵前綴Prefix uint32
}
  • TableDef 定義了表的模式：
    • Name：表名。
    • Types：列的數據類型（每個列對應一個類型）。
    • Cols：列名。
    • PKeys：主鍵列的數量，表示前 PKeys 列為主鍵。
    • Prefix：為不同表自動生成的 B 樹鍵前綴。

內部表

存儲表模式的內部表
var TDEF_TABLE = &TableDef{Prefix: 2,Name: "@table",Types: []uint32{TYPE_BYTES, TYPE_BYTES},Cols: []string{"name", "def"},PKeys: 1,
}
  • TDEF_TABLE 是一個預定義的內部表，用于存儲其他表的模式信息。
  • 結構：
    • name：表名。
    • def：表模式的 JSON 序列化內容。
  • 示例：
create table `@table` (`name` string, -- 表名`def` string, -- 模式primary key (`name`)
);
存儲元信息的內部表
var TDEF_META = &TableDef{Prefix: 1,Name: "@meta",Types: []uint32{TYPE_BYTES, TYPE_BYTES},Cols: []string{"key", "val"},PKeys: 1,
}
  • TDEF_META 是另一個預定義的內部表，用于存儲額外的元信息。
  • 結構：
    • key：鍵名。
    • val：鍵值。
  • 示例：
    create table `@meta` (`key` string, -- 鍵名`val` string, -- 鍵值primary key (`key`)
);

總結

  • 核心結構：

    • Value：單元格值，支持字符串和整數兩種類型。
    • Record：表的一行數據，包含列名和列值。
    • TableDef：表的模式定義，包括表名、列名、列類型、主鍵列數量和 B 樹前綴。

  • 內部表：

    • @table：存儲所有表的模式信息。
    • @meta：存儲數據庫的元信息，例如表前綴計數器。

這種設計使得數據庫能夠動態管理表模式和元信息，同時利用 B 樹高效地存儲和查詢數據。

獲取、更新、插入、刪除和創建操作

點查詢和更新接口

以下是用于讀取和寫入單行數據的接口定義：

func (db *DB) Get(table string, rec *Record) (bool, error)
func (db *DB) Insert(table string, rec Record) (bool, error)
func (db *DB) Update(table string, rec Record) (bool, error)
func (db *DB) Upsert(table string, rec Record) (bool, error)
func (db *DB) Delete(table string, rec Record) (bool, error)
  • Get：通過主鍵獲取一行數據。
  • Insert：僅插入新行（如果主鍵已存在，則失敗）。
  • Update：僅更新現有行（如果主鍵不存在，則失敗）。
  • Upsert：插入新行或更新現有行。
  • Delete：刪除指定行。
數據庫結構

數據庫包裝了鍵值存儲（KV）：

type DB struct {Path string // 數據庫路徑kv   KV     // 鍵值存儲接口
}
按主鍵查詢

函數 dbGet 是按主鍵查詢的核心實現。輸入的 rec 參數表示主鍵，同時也是輸出的結果行。

func dbGet(db *DB, tdef *TableDef, rec *Record) (bool, error) {// 1. 根據模式重新排列輸入列values, err := checkRecord(tdef, *rec, tdef.PKeys)if err != nil {return false, err}// 2. 編碼主鍵key := encodeKey(nil, tdef.Prefix, values[:tdef.PKeys])// 3. 查詢鍵值存儲val, ok := db.kv.Get(key)if !ok {return false, nil}// 4. 解碼值到列for i := tdef.PKeys; i < len(tdef.Cols); i++ {values[i].Type = tdef.Types[i]}decodeValues(val, values[tdef.PKeys:])rec.Cols = tdef.Colsrec.Vals = valuesreturn true, nil
}

步驟說明：

  1. 重新排序列：根據表模式重新排列輸入列，并檢查是否有缺失列。
  2. 編碼主鍵：將主鍵列編碼為字節序列。
  3. 查詢鍵值存儲：通過主鍵從鍵值存儲中獲取對應的值。
  4. 解碼值：將存儲的值解碼為列值，并填充到記錄中。
獲取表模式

用戶接口通過表名引用表，因此需要先獲取表模式。

func (db *DB) Get(table string, rec *Record) (bool, error) {tdef := getTableDef(db, table)if tdef == nil {return false, fmt.Errorf("table not found: %s", table)}return dbGet(db, tdef, rec)
}

獲取表模式的實現：

func getTableDef(db *DB, name string) *TableDef {rec := (&Record{}).AddStr("name", []byte(name))ok, err := dbGet(db, TDEF_TABLE, rec)assert(err == nil)if !ok {return nil}tdef := &TableDef{}err = json.Unmarshal(rec.Get("def").Str, tdef)assert(err == nil)return tdef
}
  • 表模式存儲在內部表 @table 中。
  • 使用 JSON 序列化和反序列化來處理表模式。

優化：可以將表模式緩存到內存中，以減少查詢次數。

插入或更新行

SQL 更新語句有三種不同的行為：

  1. INSERT：僅添加新行（如果主鍵已存在，則失敗）。
  2. UPDATE：僅修改現有行（如果主鍵不存在，則失敗）。
  3. UPSERT：添加新行或修改現有行。

實現方式是擴展 BTree.Insert 方法，增加一個模式標志：

// 更新模式
const (MODE_UPSERT       = 0 // 插入或替換MODE_UPDATE_ONLY  = 1 // 僅更新現有鍵MODE_INSERT_ONLY  = 2 // 僅添加新鍵
)type UpdateReq struct {tree *BTree// 輸出Added bool // 是否添加了新鍵// 輸入Key  []byteVal  []byteMode int
}func (tree *BTree) Update(req *UpdateReq)

核心更新邏輯：

func dbUpdate(db *DB, tdef *TableDef, rec Record, mode int) (bool, error) {values, err := checkRecord(tdef, rec, len(tdef.Cols))if err != nil {return false, err}key := encodeKey(nil, tdef.Prefix, values[:tdef.PKeys])val := encodeValues(nil, values[tdef.PKeys:])return db.kv.Update(key, val, mode)
}
  • 部分更新（讀取-修改-寫入）在更高層次（如查詢語言）實現。
創建表

創建表的過程包括以下步驟：

  1. 檢查 @table 是否存在重復表名。
  2. 從 @meta 中讀取表前綴計數器。
  3. 增加并更新表前綴計數器。
  4. 將表模式插入到 @table 中。
func (db *DB) TableNew(tdef *TableDef) error
  • 此過程涉及更新兩個鍵，因此目前缺乏原子性。可以在后續引入事務時修復此問題。

結論：基于鍵值存儲的表

基于鍵值存儲的表與傳統關系型數據庫并沒有根本區別，只是增加了數據序列化和模式管理的額外步驟。

下一步工作：

  1. 支持范圍查詢。
  2. 實現二級索引。

代碼倉庫地址：database-go

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/903186.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/903186.shtml
英文地址，請注明出處：http://en.pswp.cn/news/903186.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

2025年邵陽市工程技術研究中心申報流程、條件、獎補

2025年邵陽市工程技術研究中心申報流程、條件、獎補

一、邵陽市工程技術研究中心申報條件 &#xff08;一&#xff09;工程技術研究中心主要依托科技型企業組建&#xff0c;依托單位應具有以下條件&#xff1a; 1.?具有較強技術創新意識的領導班子和技術水平高、工程化實踐經驗豐富的工程技術研發隊伍&#xff0c;其中固定人員…
閱讀更多...
Python+AI提示詞出租車出行軌跡預測：梯度提升GBR、KNN、LR回歸、隨機森林融合及貝葉斯概率異常檢測研究

Python+AI提示詞出租車出行軌跡預測：梯度提升GBR、KNN、LR回歸、隨機森林融合及貝葉斯概率異常檢測研究

原文鏈接&#xff1a;tecdat.cn/?p41693 在當今數字化浪潮席卷全球的時代&#xff0c;城市交通領域的海量數據如同蘊藏著無限價值的寶藏等待挖掘。作為數據科學家&#xff0c;我們肩負著從復雜數據中提取關鍵信息、構建有效模型以助力決策的使命&#xff08;點擊文末“閱讀原文…
閱讀更多...
系統重裝——聯想sharkbay主板電腦

系統重裝——聯想sharkbay主板電腦

上周給一臺老電腦重裝系統系統&#xff0c;型號是lenovo sharkbay主板的電腦&#xff0c;趁著最近固態便宜&#xff0c;入手了兩塊長城的固態&#xff0c;裝上以后插上啟動U盤&#xff0c;死活進不去boot系統。提示 bootmgr 缺失&#xff0c;上網查了許久&#xff0c;終于解決了…
閱讀更多...
python連接Elasticsearch并完成增刪改查

python連接Elasticsearch并完成增刪改查

python庫提供了elasticsearch模塊，可以通過以下命令進行快速安裝，但是有個細節需要注意一下，安裝的模塊版本要跟es軟件版本一致，此處舉例：7.8.1 pip install elasticsearch==7.8.1 首先連接elasticsearch，以下是免密示例 from elasticsearch import Elasticsearch# El…
閱讀更多...
PDF嵌入圖片

PDF嵌入圖片

所需依賴 <dependency><groupId>com.itextpdf</groupId><artifactId>itext-core</artifactId><version>9.0.0</version><type>pom</type> </dependency>源碼 /*** PDF工具*/ public class PdfUtils {/*** 嵌入圖…
閱讀更多...
目標檢測篇---faster R-CNN

目標檢測篇---faster R-CNN

目標檢測系列文章 第一章 R-CNN 第二篇 Fast R-CNN 目錄 目標檢測系列文章&#x1f4c4; 論文標題&#x1f9e0; 論文邏輯梳理1. 引言部分梳理 (動機與思想) &#x1f4dd; 三句話總結&#x1f50d; 方法邏輯梳理&#x1f680; 關鍵創新點&#x1f517; 方法流程圖關鍵疑問解答…
閱讀更多...
Seaborn模塊練習題

Seaborn模塊練習題

1.使用tips數據集&#xff0c;創建一個展示不同時間段(午餐/晚餐)賬單總額分布的箱線圖 import seaborn as sns import matplotlib.pyplot as plt import pandas as pdsns.set_style("darkgrid") plt.rcParams["axes.unicode_minus"] Falsetips pd.read…
閱讀更多...
計算機網絡 | 應用層（1）--應用層協議原理

計算機網絡 | 應用層（1）--應用層協議原理

&#x1f493;個人主頁&#xff1a;mooridy &#x1f493;專欄地址&#xff1a;《計算機網絡&#xff1a;自定向下方法》 大綱式閱讀筆記 關注我&#x1f339;&#xff0c;和我一起學習更多計算機的知識 &#x1f51d;&#x1f51d;&#x1f51d; 目錄 1. 應用層協議原理 1.1 …
閱讀更多...
論文導讀 - 基于大規模測量與多任務深度學習的電子鼻系統實現目標識別、濃度預測與狀態判斷

論文導讀 - 基于大規模測量與多任務深度學習的電子鼻系統實現目標識別、濃度預測與狀態判斷

基于大規模測量與多任務深度學習的電子鼻系統實現目標識別、濃度預測與狀態判斷 原論文地址&#xff1a;https://www.sciencedirect.com/science/article/abs/pii/S0925400521014830 引用此論文&#xff08;GB/T 7714-2015&#xff09;&#xff1a; WANG T, ZHANG H, WU Y, …
閱讀更多...
React中createPortal 的詳細用法

React中createPortal 的詳細用法

createPortal 是 React 提供的一個實用工具&#xff0c;用于將 React 子元素渲染到 DOM 中的某個位置&#xff0c;而該位置與父組件不在同一個 DOM 層次結構中。這在某些特殊場景下非常有用&#xff0c;比如實現模態框、彈出菜單、固定定位元素等功能。 基本語法 JavaScript …
閱讀更多...
電池的壽命

電池的壽命

思路&#xff1a; 首先&#xff0c;我們觀察發現&#xff1a;由于每枚電池的使用時間不同&#xff0c;而我們又要減少浪費才能使所有電池加起來用得最久&#xff0c;不難發現&#xff1a;當n2時&#xff0c;輸出較小值。 第一步&#xff1a;將電池分為兩組&#xff0c;使兩組…
閱讀更多...
LeetCode每日一題4.27

LeetCode每日一題4.27

3392. 統計符合條件長度為 3 的子數組數目 問題 問題分析 統計符合條件的長度為 3 的子數組數目。具體條件是&#xff1a;子數組的第一個數和第三個數的和恰好為第二個數的一半。 思路 遍歷數組&#xff1a;由于子數組長度固定為 3&#xff0c;我們可以通過遍歷數組來檢查每…
閱讀更多...
Linux日志處理命令多管道實戰應用

Linux日志處理命令多管道實戰應用

全文目錄 1 日志處理1.1 實時日志分析1.1.1 nginx日志配置1.1.2 nginx日志示例1.1.3 日志分析示例 1.2 多文件合并分析1.3 時間范圍日志提取 2 問題追查2.1 進程級問題定位2.2 網絡連接排查2.3 硬件故障追蹤 3 數據統計3.1 磁盤空間預警3.2 進程資源消耗排名3.3 HTTP狀態碼統計…
閱讀更多...
0803分頁_加載更多-網絡ajax請求2-react-仿低代碼平臺項目

0803分頁_加載更多-網絡ajax請求2-react-仿低代碼平臺項目

文章目錄 1 分頁1.1 url與分頁參數1.2 分頁組件與url1.3 列表頁引用分頁組件 2 加載更多2.1 狀態2.2 觸發時機2.3 加載數據2.4優化 結語 1 分頁 1.1 url與分頁參數 查詢問卷列表接口&#xff0c;添加分頁參數&#xff1a; page&#xff1a;當前頁碼&#xff08;第幾頁&#…
閱讀更多...
【技術追蹤】基于擴散模型的腦圖像反事實生成與異常檢測（TMI-2024）

【技術追蹤】基于擴散模型的腦圖像反事實生成與異常檢測（TMI-2024）

一種新穎的擴散模型雙重采樣策略&#xff0c;DDPM DDIM ~ 論文&#xff1a;Diffusion Models for Counterfactual Generation and Anomaly Detection in Brain Images 0、摘要 病理區域的分割掩模在許多醫學應用中很有用&#xff0c;例如腦腫瘤和中風管理。此外&#xff0c;疾…
閱讀更多...
第十六屆藍橋杯大賽軟件賽省賽第二場 C/C++ 大學 A 組

第十六屆藍橋杯大賽軟件賽省賽第二場 C/C++ 大學 A 組

比賽還沒有開始&#xff0c;竟然忘記寫using namespace std; //debug半天沒看明白 (平時cv多了 然后就是忘記那個編譯參數&#xff0c;&#xff08;好慘的開局 編譯參數-stdc11 以下都是賽時所寫代碼&#xff0c;賽時無聊時把思路都打上去了&#xff08;除了倒數第二題&#…
閱讀更多...
CentOS 7上Memcached的安裝、配置及高可用架構搭建

CentOS 7上Memcached的安裝、配置及高可用架構搭建

Memcached是一款高性能的分布式內存緩存系統&#xff0c;常用于加速動態Web應用的響應。本文將在CentOS 7上詳細介紹Memcached的安裝、配置&#xff0c;以及如何實現Memcached的高可用架構。 &#xff08;1&#xff09;、搭建memcached 主主復制架構 Memcached 的復制功能支持…
閱讀更多...
告別進度失控：用燃盡圖補上甘特圖的監控盲區

告別進度失控：用燃盡圖補上甘特圖的監控盲區

在職場中&#xff0c;項目經理最頭疼的莫過于“計劃趕不上變化”。明明用甘特圖排好了時間表&#xff0c;任務卻總像脫韁野馬——要么進度滯后&#xff0c;要么資源分配失衡。甘特圖雖能直觀展示任務時間軸&#xff0c;但面對突發風險或團隊效率波動時&#xff0c;它更像一張“…
閱讀更多...
爬蟲-oiwiki

爬蟲-oiwiki

我們將BASE_URL 設置為 "https://oi-wiki.org/" 后腳本就會自動開始抓取該url及其子頁面的所有內容&#xff0c;并將統一子頁面的放在一個文件夾中 import requests from bs4 import BeautifulSoup from urllib.parse import urljoin, urlparse import os import pd…
閱讀更多...
業務中臺與數據中臺：企業數字化轉型的核心引擎

業務中臺與數據中臺：企業數字化轉型的核心引擎

前言&#xff1a;在當今數字化浪潮下&#xff0c;企業為了提升運營效率、加速創新步伐并更好地適應市場變化&#xff0c;業務中臺與數據中臺應運而生&#xff0c;成為企業架構中的關鍵組成部分。本文將深入探討業務中臺和數據中臺的簡介、發展史、技術流環節以及在實際生產中的…
閱讀更多...
最新文章

Copyright @ 2022~2023