數(shù)據(jù)模型和數(shù)據(jù)庫(kù)
一、數(shù)據(jù)庫(kù)
數(shù)據(jù)庫(kù)是一個(gè)有組織的相互關(guān)聯(lián)的數(shù)據(jù)集合扛施，它對(duì)現(xiàn)實(shí)世界的某些方面進(jìn)行建模。人們經(jīng)常將"數(shù)據(jù)庫(kù)"與"數(shù)據(jù)庫(kù)管理系統(tǒng)"(例如屹篓，MySQL疙渣、Oracle、MongoDB)混淆堆巧。數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS)是管理數(shù)據(jù)庫(kù)的軟件妄荔。
二、扁平化的文件形式?
數(shù)據(jù)庫(kù)被存儲(chǔ)為DBMS管理的逗號(hào)分隔的值（CSV）文件谍肤。每個(gè)實(shí)體將被存儲(chǔ)在自己的文件中啦租。應(yīng)用程序每次要讀取或更新記錄時(shí)，都必須解析文件荒揣。每個(gè)實(shí)體都有自己的屬性集篷角，所以在每個(gè)文件中，不同的記錄用新的行來(lái)分隔系任，而記錄中每個(gè)相應(yīng)的屬性都用逗號(hào)來(lái)分隔恳蹲。
扁平化文件的問(wèn)題：
1.不能保證數(shù)據(jù)的完整性
2.實(shí)施及擴(kuò)展性較差：新建時(shí)需重寫物理層
3.耐用性較差
三、數(shù)據(jù)庫(kù)管理系統(tǒng)
DBMS是一種軟件俩滥，允許應(yīng)用程序在數(shù)據(jù)庫(kù)中存儲(chǔ)和分析信息嘉蕾。一個(gè)通用的DBMS被設(shè)計(jì)為允許定義、創(chuàng)建霜旧、查詢错忱、更新和管理數(shù)據(jù)庫(kù)。
早期的DBMS：數(shù)據(jù)庫(kù)應(yīng)用很難建立和維護(hù)挂据，因?yàn)檫壿媽雍臀锢韺又g存在著緊密的耦合航背。邏輯層描述了數(shù)據(jù)庫(kù)有哪些實(shí)體和屬性，而物理層是這些實(shí)體和屬性的存儲(chǔ)方式棱貌。早期玖媚，物理層是在應(yīng)用程序代碼中定義的，所以如果我們想改變應(yīng)用程序正在使用的物理層婚脱，我們將必須改變所有的代碼來(lái)匹配新的物理層今魔。
四、數(shù)據(jù)模型：概念模型+邏輯模型+物理模型
客觀對(duì)象的抽象過(guò)程---兩步抽象：現(xiàn)實(shí)世界中的客觀對(duì)象抽象為概念模型(將現(xiàn)實(shí)世界抽象為信息世界)障贸；概念模型轉(zhuǎn)換為某一數(shù)據(jù)庫(kù)管理系統(tǒng)支持的數(shù)據(jù)模型(將信息世界轉(zhuǎn)換為機(jī)器世界)错森。
Ⅰ 概念模型: 實(shí)體-聯(lián)系?（Entity-Relationship，ER圖）
按用戶的觀點(diǎn)來(lái)對(duì)數(shù)據(jù)和信息建模篮洁，用于數(shù)據(jù)庫(kù)設(shè)計(jì)涩维。
Ⅱ 邏輯模型和物理模型??
*邏輯模型主要包括網(wǎng)狀模型、層次模型、關(guān)系模型瓦阐、面向?qū)ο髷?shù)據(jù)模型蜗侈、對(duì)象關(guān)系數(shù)據(jù)模型、半結(jié)構(gòu)化數(shù)據(jù)模型等睡蟋。按計(jì)算機(jī)系統(tǒng)的觀點(diǎn)對(duì)數(shù)據(jù)建模踏幻，用于DBMS實(shí)現(xiàn)。
*物理模型是對(duì)數(shù)據(jù)最底層的抽象戳杀，描述數(shù)據(jù)在系統(tǒng)內(nèi)部的表示方式和存取方法该面，在磁盤或磁帶上的存儲(chǔ)方式和存取方法。
Ⅲ 常用的數(shù)據(jù)模型
①層次模型（Hierarchical Model）：用樹形結(jié)構(gòu)來(lái)表示各類實(shí)體以及實(shí)體間的聯(lián)系?
②網(wǎng)狀模型（Network Model）
③關(guān)系模型（Relational Model)）
④面向?qū)ο髷?shù)據(jù)模型（Object Oriented Data Model）
⑤對(duì)象關(guān)系數(shù)據(jù)模型（Object Relational Data Model）
⑥半結(jié)構(gòu)化數(shù)據(jù)模型（Semistruture Data Model）
關(guān)系模型：避免改變物理層時(shí)需重寫DBMS的尷尬情況
*關(guān)系（Relation）：一個(gè)關(guān)系對(duì)應(yīng)通常說(shuō)的一張表
*元組（Tuple）：表中的一行即為一個(gè)元組信卡；笛卡爾積中每一個(gè)元素
*屬性（Attribute）：表中的一列即為一個(gè)屬性隔缀，給每一個(gè)屬性起一個(gè)名稱即屬性名
*候選碼（Candidate key）：若關(guān)系中的某一屬性組的值能唯一地標(biāo)識(shí)一個(gè)元組，則稱該屬性組為候選碼
*主碼（Key）：若一個(gè)關(guān)系有多個(gè)候選碼傍菇，則選定其中一個(gè)為主碼（Primary key）
*主屬性:候選碼的諸屬性稱為主屬性（Prime attribute）不包含在任何侯選碼中的屬性稱為非主屬性（Non-Prime attribute）或非碼屬性（Non-key attribute）
*域（Domain）：是一組具有相同數(shù)據(jù)類型的值的集合蚕泽。屬性的取值范圍來(lái)自某個(gè)域。
*分量：元組中的一個(gè)屬性值桥嗤；n笛卡爾積元素（d1，d2仔蝌，…泛领，dn）中的每一個(gè)值di?
*關(guān)系模式：對(duì)關(guān)系的描述
關(guān)系名（屬性1，屬性2敛惊，…渊鞋，屬性n）
學(xué)生（學(xué)號(hào)，姓名瞧挤，年齡锡宋，性別，系名特恬，年級(jí)）
數(shù)據(jù)模型是描述數(shù)據(jù)庫(kù)中數(shù)據(jù)的概念的集合执俩。關(guān)系模型是數(shù)據(jù)模型的一個(gè)例子。模式是對(duì)一個(gè)特定的數(shù)據(jù)集合的描述﹐使用一個(gè)給定的數(shù)據(jù)模型癌刽。關(guān)系型數(shù)據(jù)模型定義了三個(gè)概念：
*結(jié)構(gòu)：關(guān)系的定義和它們的內(nèi)容役首，這是關(guān)系所具有的屬性和這些屬性所能持有的值。
*完整性：確保數(shù)據(jù)庫(kù)的內(nèi)容滿足約束條件显拜，一個(gè)約束的例子是：年份屬性的任何值都必須是數(shù)字衡奥。①實(shí)體完整性②參照完整性③用戶定義的完整性
*操縱：如何訪問(wèn)和修改數(shù)據(jù)庫(kù)的內(nèi)容。
五远荠、結(jié)構(gòu)化查詢語(yǔ)言（Structured Query Language矮固，SQL）
1、DML(data manipulation language)譬淳，數(shù)據(jù)庫(kù)操縱語(yǔ)言：SELECT档址、UPDATE盹兢、INSERT、DELETE辰晕、CALL蛤迎、EXPLAIN PLAN、LOCK TABLE
一種從數(shù)據(jù)庫(kù)中存儲(chǔ)和檢索信息的語(yǔ)言含友。這方面有兩類語(yǔ)言：
*程序性的替裆。查詢指定了DBMS應(yīng)該用來(lái)尋找所需結(jié)果的（高級(jí)）策略。
*非程序性(聲明性)窘问。查詢只指定想要什么數(shù)據(jù)辆童，而不是如何找到它。
2惠赫、DDL（data definition language）把鉴，數(shù)據(jù)庫(kù)定義語(yǔ)言：CREATE、ALTER儿咱、DROP
在創(chuàng)建表的時(shí)候用到的一些sql庭砍，DDL主要是用在定義或改變表的結(jié)構(gòu)，數(shù)據(jù)類型混埠，表之間的鏈接和約束等初始化工作上
3怠缸、DCL（Data Control Language），數(shù)據(jù)庫(kù)控制語(yǔ)言：GRANT钳宪、DENY揭北、REVOKE
用來(lái)設(shè)置或更改數(shù)據(jù)庫(kù)用戶或角色權(quán)限的語(yǔ)句
六、關(guān)系代數(shù)
關(guān)系代數(shù)是一組基本操作吏颖，用于檢索和處理關(guān)系中的圖元搔体。每個(gè)運(yùn)算符都接受一個(gè)或多個(gè)關(guān)系作為輸入，并輸出一個(gè)新的關(guān)系半醉。為了編寫查詢疚俱，我們可以將這些運(yùn)算符"連鎖"起來(lái)，以創(chuàng)建更復(fù)雜的操作缩多。
（1）選擇：Select接收一個(gè)關(guān)系计螺，并從該關(guān)系中輸出一個(gè)滿足選擇謂詞的圖元的子集。謂詞的作用就像一個(gè)過(guò)濾器瞧壮，我們可以使用連接詞和非連接詞來(lái)組合多個(gè)謂詞登馒。
語(yǔ)法︰opredicate(R)
（2）投影：投影接收一個(gè)關(guān)系并輸出一個(gè)只包含指定屬性的圖元的關(guān)系，你可以在輸入的關(guān)系中重新安排屬性的順序咆槽，也可以對(duì)值進(jìn)行操作陈轿。
語(yǔ)法：πA1,A2...An(R)
（3）笛卡爾積：接收兩個(gè)關(guān)系，并輸出一個(gè)包含輸入關(guān)系中所有可能組合的圖元的關(guān)系（不能重復(fù)）。
語(yǔ)法：(RxS)
（4）并（Union）：Union接收兩個(gè)關(guān)系并輸出一個(gè)關(guān)系麦射，該關(guān)系包含至少出現(xiàn)在一個(gè)輸入關(guān)系中的所有圖元蛾娶。注意∶這兩個(gè)輸入關(guān)系必須有完全相同的屬性。
語(yǔ)法：(RUS)
（5）交：交接收兩個(gè)關(guān)系并輸出一個(gè)包含所有出現(xiàn)在兩個(gè)輸入關(guān)系中的圖元的關(guān)系潜秋。注意︰這兩個(gè)輸入關(guān)系必須有完全相同的屬性隅居。
語(yǔ)法：(R∩S)
（6）差：Difference接收兩個(gè)關(guān)系并輸出一個(gè)關(guān)系羡洛，這個(gè)關(guān)系包含所有出現(xiàn)在第一個(gè)關(guān)系中但沒有出現(xiàn)在第二個(gè)關(guān)系中的圖元丈屹。注意︰兩個(gè)輸入關(guān)系必須有完全相同的屬性乱豆。
語(yǔ)法。(R-S)
（7）連接：Join接收兩個(gè)關(guān)系并輸出一個(gè)關(guān)系钩述，該關(guān)系包含兩個(gè)圖元的所有組合寨躁。其中對(duì)于兩個(gè)關(guān)系共享的每個(gè)屬性，兩個(gè)圖元的該屬性的值是相同的牙勘。
語(yǔ)法：(Rt><JS)
七职恳、數(shù)據(jù)庫(kù)系統(tǒng)的結(jié)構(gòu)
1、從數(shù)據(jù)庫(kù)應(yīng)用開發(fā)人員角度看方面，數(shù)據(jù)庫(kù)系統(tǒng)通常采用三級(jí)模式結(jié)構(gòu)放钦，是數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)部的系統(tǒng)結(jié)構(gòu)?
①模式（Schema）/邏輯模式：數(shù)據(jù)庫(kù)系統(tǒng)模式結(jié)構(gòu)的中間層，是數(shù)據(jù)的全局邏輯結(jié)構(gòu)
*數(shù)據(jù)庫(kù)中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述
*所有用戶的公共數(shù)據(jù)視圖
*與數(shù)據(jù)的物理存儲(chǔ)細(xì)節(jié)和硬件環(huán)境無(wú)關(guān)
*與具體的應(yīng)用程序恭金、開發(fā)工具及高級(jí)程序設(shè)計(jì)語(yǔ)言無(wú)關(guān)
②外模式（External Schema）/子模式/用戶模式：是數(shù)據(jù)的局部邏輯結(jié)構(gòu)
*數(shù)據(jù)庫(kù)用戶（包括應(yīng)用程序員和最終用戶）使用的局部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述
*數(shù)據(jù)庫(kù)用戶的數(shù)據(jù)視圖操禀，是與某一應(yīng)用有關(guān)的數(shù)據(jù)的邏輯表示
③內(nèi)模式（Internal Schema）/?存儲(chǔ)模式：一個(gè)數(shù)據(jù)庫(kù)只有一個(gè)內(nèi)模式
*數(shù)據(jù)物理結(jié)構(gòu)和存儲(chǔ)方式的描述
*數(shù)據(jù)在數(shù)據(jù)庫(kù)內(nèi)部的表示方式
l記錄的存儲(chǔ)方式（例如，順序存儲(chǔ)蔚叨，按照B樹結(jié)構(gòu)存儲(chǔ)，按hash方法存儲(chǔ)等）
l索引的組織方式
l數(shù)據(jù)是否壓縮存儲(chǔ)
l數(shù)據(jù)是否加密
l數(shù)據(jù)存儲(chǔ)記錄結(jié)構(gòu)的規(guī)定
2辙培、從數(shù)據(jù)庫(kù)最終用戶角度看蔑水，數(shù)據(jù)庫(kù)系統(tǒng)的結(jié)構(gòu)分為:
①單用戶結(jié)構(gòu)
②主從式結(jié)構(gòu)
③分布式結(jié)構(gòu)
④客戶-服務(wù)器
⑤瀏覽器-應(yīng)用服務(wù)器／數(shù)據(jù)庫(kù)服務(wù)器多層結(jié)構(gòu)等
02 中級(jí)SQL
一、關(guān)系型語(yǔ)言SQL
二扬蕊、SQL歷史
關(guān)系型數(shù)據(jù)庫(kù)的聲明式查詢語(yǔ)言搀别。它最初是在20世紀(jì)70年代作為IBM系統(tǒng)R項(xiàng)目的一部分而開發(fā)的。IBM最初稱它為"SEQUEL”(結(jié)構(gòu)化英語(yǔ)查詢語(yǔ)言)尾抑。該名稱在20世紀(jì)80年代改為"SQL”(結(jié)構(gòu)化查詢語(yǔ)言)歇父。該語(yǔ)言是由不同類別的命令組成的：
1.? ?數(shù)據(jù)操作語(yǔ)言(DML)。SELECT再愈，INSERT榜苫，UPDATE，和DELETE語(yǔ)句翎冲。
2．?dāng)?shù)據(jù)定義語(yǔ)言(DDL)垂睬。表、索引、視圖和其他對(duì)象的模式定義驹饺。
3．?dāng)?shù)據(jù)控制語(yǔ)言(DCL)钳枕。安全，訪問(wèn)控制赏壹。
SQL不是一種死的語(yǔ)言鱼炒。它每隔幾年就會(huì)有新的功能被更新。SQL92是一個(gè)DBMS必須支持的最低限度蝌借，以聲稱他們支持SQL昔瞧。每個(gè)供應(yīng)商都在一定程度上遵循該標(biāo)準(zhǔn)，但也有許多專有的擴(kuò)展骨望。
三硬爆、連接join
從一個(gè)或多個(gè)表組合列并生成一個(gè)新表。用于表示涉及跨多個(gè)表的數(shù)據(jù)的查詢擎鸠。
四缀磕、聚合
聚合函數(shù)接收一袋元組作為其輸入，然后產(chǎn)生一個(gè)單一的標(biāo)量值作為其輸出劣光，聚合函數(shù)幾乎只能在SELECT輸出列表中使用袜蚕。
*AVG(COL)。COL中數(shù)值的平均值
*MIN(COL)绢涡。COL中的最小值
*MAX(COL)牲剃。COL中的最大值
*COUNT(COL)。關(guān)系中的圖元數(shù)
五雄可、字符串操作
SQL標(biāo)準(zhǔn)規(guī)定字符串只區(qū)分大小寫和單引號(hào)凿傅。有些函數(shù)可以用于查詢的任何部分。
1.模式匹配：
LIKE關(guān)鍵字用于謂詞中的字符串匹配数苫。
"%"匹配任何子字符串(包括空子字符串)聪舒。
"_"與任何一個(gè)字符匹配。
連接："||"將兩個(gè)或多個(gè)字符串連接到一個(gè)字符串中虐急。
2.字符串函數(shù)
substring(S,B,E)? ?UPPER(S)
六箱残、日期和時(shí)間
七、輸出重定向
DBMS將結(jié)果存儲(chǔ)到另一個(gè)表中止吁，而不是將結(jié)果返回給客戶端(例如終端)被辑。然后可以在后續(xù)查詢中訪問(wèn)此數(shù)據(jù)。
存入新表：select ... into newtable from ......;
存入舊表(相同列數(shù)和類型)：INSERT INTO 舊表 (SELECT ... FROM ...)敬惦。
八盼理、輸出控制
order by ASC/DESC
limit? number：限制結(jié)果元組的數(shù)量?
limit number1 offset number2 : 限制數(shù)量為number1，偏移量為number2
除非我們有限制地使用ORDERBY子句俄删，否則DBMS可能在每次調(diào)用查詢時(shí)在結(jié)果中產(chǎn)生不同的元組榜揖，因?yàn)殛P(guān)系模型不強(qiáng)制排序勾哩。
九、嵌套查詢
調(diào)用其他查詢中的查詢举哟，在單個(gè)查詢中執(zhí)行更復(fù)雜的邏輯思劳。嵌套查詢通常很難優(yōu)化。外部查詢的范圍包含在內(nèi)部查詢中(即內(nèi)部查詢可以從外部查詢?cè)L問(wèn)屬性)妨猩，而不是反過(guò)來(lái)潜叛。內(nèi)部查詢幾乎可以出現(xiàn)在查詢的任何部分。
嵌套查詢結(jié)果表達(dá)式：
ALL：必須滿足子查詢中所有行的表達(dá)式壶硅。
Any：必須滿足子查詢中至少一行的表達(dá)式.
IN：等效于=any()威兜。
EXISTS: 至少返回一行。
十庐椒、窗口功能
在一組相關(guān)的元組上執(zhí)行“滑動(dòng)”計(jì)算椒舵，就像聚合一樣，但是元組不是分組在一個(gè)輸出元組中约谈。
函數(shù)：窗口函數(shù)可以是我們前面討論過(guò)的任何聚合函數(shù)笔宿。還有一些特殊的窗口功能：
1.ROW_Number：當(dāng)前行的編號(hào)。
2.RANK：當(dāng)前行的順序位置棱诱。
分組：over子句指定如何在計(jì)算窗口功能時(shí)將元組分組泼橘。使用PARTITION BY 指定組。
十一迈勋、常見的表格表達(dá)式
在編寫更復(fù)雜的查詢時(shí)炬灭，通用表表達(dá)式(CTE)是窗口或嵌套查詢的一種替代方法。它們提供了一種在大型查詢中為用戶編寫輔助語(yǔ)句的方法靡菇。CTEs可以被認(rèn)為是一個(gè)臨時(shí)表重归，它的范圍是一個(gè)單一的查詢。
WITH子句將內(nèi)部查詢的輸出與一個(gè)具有該名稱的臨時(shí)結(jié)果綁定
SQL homework
sqlite3是linux上的小巧的數(shù)據(jù)庫(kù)厦凤，一個(gè)文件就是一個(gè)數(shù)據(jù)庫(kù)鼻吮。
1.查看所有表：
2.查看單個(gè)表聲明：
3.執(zhí)行sql文件：
03 數(shù)據(jù)庫(kù)存儲(chǔ)一
一、存儲(chǔ)
Volatile Devices（易失設(shè)備）：
*易失意味著如果你切斷了電源泳唠，數(shù)據(jù)將會(huì)丟失狈网。
*易失存儲(chǔ)支持以字節(jié)為單位的快速的隨機(jī)訪問(wèn)宙搬。這意味著程序可以跳到任何字節(jié)地址并獲得這里的數(shù)據(jù)笨腥。
*出于我們的目的，我們總是將這個(gè)存儲(chǔ)稱為“內(nèi)存”（memory）勇垛。
Non-Volatile Devices（非易失設(shè)備）：
*非易失意味著存儲(chǔ)設(shè)備不需要提供持久的電力去保持?jǐn)?shù)據(jù)的存儲(chǔ)脖母。
*它以塊/頁(yè)為單位。這意味著為了讀取一個(gè)特定偏移的數(shù)據(jù)闲孤，程序需要先讀取4KB的頁(yè)到內(nèi)存中谆级，并從內(nèi)存中讀取這個(gè)數(shù)據(jù)烤礁。
*非易失存儲(chǔ)在原理上（設(shè)計(jì)上）對(duì)順序訪問(wèn)速度快（它可以同時(shí)讀取多個(gè)連續(xù)的數(shù)據(jù)塊）。
*我們將它稱為“硬盤”（disk）肥照。但我們不會(huì)區(qū)分固態(tài)硬盤（SSD）和機(jī)械硬盤（HDD）脚仔。
二、面向磁盤的DBMS概述
數(shù)據(jù)庫(kù)都在磁盤上舆绎，數(shù)據(jù)庫(kù)文件中的數(shù)據(jù)被組織成頁(yè)鲤脏，第一頁(yè)是目錄頁(yè)。為了對(duì)數(shù)據(jù)進(jìn)行操作吕朵，DBMS需要將數(shù)據(jù)引入內(nèi)存猎醇。它通過(guò)擁有一個(gè)緩沖池來(lái)管理數(shù)據(jù)在磁盤和內(nèi)存之間的來(lái)回移動(dòng)。DBMS也有一個(gè)執(zhí)行引擎努溃，將執(zhí)行查詢硫嘶。執(zhí)行引擎將要求緩沖池提供一個(gè)特定的頁(yè)面，而緩沖池將負(fù)責(zé)把該頁(yè)面帶入內(nèi)存梧税，并給執(zhí)行引擎一個(gè)指向內(nèi)存中該頁(yè)面的指針沦疾。緩沖池管理器將確保該頁(yè)的存在，同時(shí)執(zhí)行引擎對(duì)該部分內(nèi)存進(jìn)行操作贡蓖。
三曹鸠、數(shù)據(jù)庫(kù) vs 操作系統(tǒng)
數(shù)據(jù)庫(kù)的一個(gè)高層的設(shè)計(jì)目標(biāo)是支持?jǐn)?shù)據(jù)庫(kù)存儲(chǔ)的數(shù)據(jù)大小超過(guò)可用內(nèi)存的大小。讀取/寫入數(shù)據(jù)到硬盤中是一個(gè)非常低效的操作斥铺，所以我們必須管理好這些操作彻桃。我們不希望從硬盤讀取數(shù)據(jù)的時(shí)候出現(xiàn)大的空擋從而拖慢其他操作的速度。同時(shí)我們希望數(shù)據(jù)庫(kù)在等待數(shù)據(jù)讀取的時(shí)候可以同時(shí)運(yùn)行其他查詢晾蜘。
這個(gè)高層的設(shè)計(jì)目標(biāo)像虛擬內(nèi)存邻眷，在虛擬內(nèi)存中有一個(gè)較大的地址空間和一個(gè)供操作系統(tǒng)從磁盤引入頁(yè)面的位置。
實(shí)現(xiàn)虛擬內(nèi)存的一種方式是使用mmap去映射一個(gè)文件的內(nèi)容到一個(gè)內(nèi)存地址空間剔交，操作系統(tǒng)負(fù)責(zé)從硬盤和內(nèi)存之間移動(dòng)頁(yè)肆饶。但不幸的是，如果mmap遇到頁(yè)錯(cuò)誤岖常，進(jìn)程將被阻塞驯镊。如果你要寫頁(yè)，你永遠(yuǎn)不要考慮在數(shù)據(jù)庫(kù)中使用mmap竭鞍。
數(shù)據(jù)庫(kù)總是希望自己可以控制操作板惑，并且可以做的更好，因?yàn)樗烙心男?shù)據(jù)將要被訪問(wèn)偎快，有哪些查詢將要被運(yùn)行冯乘。
操作系統(tǒng)支持以下操作：
madvise：告訴操作系統(tǒng)什么時(shí)候你計(jì)劃讀取特定的頁(yè)。
mlock：告訴操作系統(tǒng)不要將內(nèi)存交換到硬盤上晒夹。
msync：告訴操作系統(tǒng)同步內(nèi)存的內(nèi)容到硬盤上裆馒。
出于正確性和性能原因姊氓，我們不建議在數(shù)據(jù)庫(kù)中使用mmap。即使系統(tǒng)也提供一些看起來(lái)類似的功能喷好，但數(shù)據(jù)庫(kù)自己實(shí)現(xiàn)這些功能可以控制的更好翔横，并且能獲得更好的性能。
四梗搅、文件存儲(chǔ)
在最基本的形式中棕孙，數(shù)據(jù)庫(kù)將數(shù)據(jù)存成文件。一些數(shù)據(jù)庫(kù)可能使用文件層次結(jié)構(gòu)（多文件）些膨，另一些可能使用單文件（例如SQLite）蟀俊。
但操作系統(tǒng)不知道這些文件內(nèi)容的意義，只有數(shù)據(jù)庫(kù)知道如何解密這些文件订雾，因?yàn)檫@些文件是數(shù)據(jù)庫(kù)由特定的方式編碼的肢预。
數(shù)據(jù)庫(kù)的存儲(chǔ)管理器負(fù)責(zé)管理數(shù)據(jù)文件。它將文件表示為頁(yè)的集合洼哎。它還跟蹤哪些數(shù)據(jù)被讀寫到頁(yè)中烫映，以及頁(yè)中有多少空閑的空間。
五噩峦、數(shù)據(jù)庫(kù)的頁(yè)
數(shù)據(jù)庫(kù)將數(shù)據(jù)組織在一個(gè)或多個(gè)文件中锭沟，這些文件在存儲(chǔ)在頁(yè)中，他們具有固定大小的塊识补。頁(yè)中可以包括不同類別的數(shù)據(jù)（元組族淮，索引）。當(dāng)然大多數(shù)系統(tǒng)不會(huì)在一個(gè)頁(yè)中混合存儲(chǔ)這些類別凭涂。一些系統(tǒng)可能會(huì)要求頁(yè)是自我包含的（self-contained）祝辣，這意味著讀取頁(yè)的信息在頁(yè)本身中。
每個(gè)頁(yè)都有一個(gè)唯一的標(biāo)識(shí)符切油。如果數(shù)據(jù)是單文件的蝙斜，那頁(yè)id可以是簡(jiǎn)單的用偏移表示。大多數(shù)數(shù)據(jù)庫(kù)都有一個(gè)中間層來(lái)映射頁(yè)id到文件路徑和偏移的對(duì)應(yīng)關(guān)系澎胡。高層的系統(tǒng)會(huì)直接詢問(wèn)特定的頁(yè)id孕荠，存儲(chǔ)管理器將會(huì)轉(zhuǎn)換頁(yè)id到文件路徑和偏移并去尋找這個(gè)頁(yè)。
大多數(shù)數(shù)據(jù)庫(kù)使用固定長(zhǎng)度的頁(yè)去避免支持可變長(zhǎng)度的頁(yè)所需的工程開銷攻谁。例如稚伍，使用可變長(zhǎng)度的頁(yè)，刪除一個(gè)頁(yè)可能會(huì)造成文件的一個(gè)碎片巢株，數(shù)據(jù)庫(kù)并不能很輕易的使用新的頁(yè)填充這個(gè)碎片（比如大小過(guò)小槐瑞，造成新的碎片等等）熙涤。
這里有3個(gè)數(shù)據(jù)庫(kù)中page的概念：
①硬件的頁(yè)（通常為4KB）
②操作系統(tǒng)的頁(yè)（4KB）
③數(shù)據(jù)庫(kù)的頁(yè)（1-16KB）
存儲(chǔ)設(shè)備保證對(duì)硬件的頁(yè)大小的數(shù)據(jù)原子寫操作阁苞。如果硬件的頁(yè)是4KB困檩，操作系統(tǒng)嘗試去寫4KB到硬盤中，這4KB要不完全寫入成功那槽，要不完全寫入失數垦亍（不存在寫入部分成功的情況）。這意味著如果數(shù)據(jù)庫(kù)的頁(yè)大于硬件的頁(yè)骚灸，數(shù)據(jù)庫(kù)將會(huì)使用額外的操作去保證安全的寫入數(shù)據(jù)糟趾。因?yàn)楫?dāng)系統(tǒng)崩潰時(shí)，程序可能寫入了部分?jǐn)?shù)據(jù)甚牲。
六义郑、數(shù)據(jù)庫(kù)的堆
數(shù)據(jù)庫(kù)有2種方式可以找到頁(yè)在硬盤上的位置，堆文件組織是一種方式丈钙。
一個(gè)堆文件是一個(gè)頁(yè)面的無(wú)序集合非驮，其中元組以隨機(jī)的順序存儲(chǔ)。
數(shù)據(jù)庫(kù)可以使用鏈表或頁(yè)字典的方式通過(guò)頁(yè)id來(lái)定位頁(yè)在硬盤上的位置雏赦。
**Linked List（鏈表）：**頭部的頁(yè)有一個(gè)指向空閑頁(yè)的指針和一個(gè)數(shù)據(jù)頁(yè)的指針劫笙。然而，如果數(shù)據(jù)庫(kù)正在尋找一個(gè)特定的頁(yè)星岗，他需要順序掃描數(shù)據(jù)頁(yè)直到該頁(yè)被找到填大。
**Page Directory（頁(yè)字典）：**數(shù)據(jù)庫(kù)維護(hù)一個(gè)特殊的頁(yè)，它存儲(chǔ)著每個(gè)數(shù)據(jù)頁(yè)的位置以及每個(gè)頁(yè)上的空閑空間俏橘。
七允华、頁(yè)布局
每個(gè)頁(yè)包含一個(gè)頭部記錄著每個(gè)頁(yè)的元信息：
*頁(yè)大小
*校驗(yàn)和
*數(shù)據(jù)庫(kù)版本
*事務(wù)可見性
*是否自我包含（比如Oracle需要這個(gè)）
布局?jǐn)?shù)據(jù)的一種方法是跟蹤有多少元組存儲(chǔ)在一個(gè)頁(yè)中，并在每次添加新元組時(shí)追加到尾部寥掐。然而例获，當(dāng)元組被刪除或者元組有變長(zhǎng)屬性的情況下問(wèn)題就出現(xiàn)了。
有2種主要的方法在page中布局?jǐn)?shù)據(jù)：（1）槽頁(yè)（2）日志結(jié)構(gòu)
**Slotted Pages（槽頁(yè)）：**頁(yè)映射槽到偏移曹仗。
*頭記錄使用槽的數(shù)量榨汤、最后使用的槽的起始位置和一個(gè)跟蹤了每個(gè)槽的起始位置的槽數(shù)組。
*當(dāng)插入一個(gè)元組的時(shí)候怎茫，槽數(shù)組將從前往后插入收壕，元組數(shù)據(jù)將從后往前插入。當(dāng)槽數(shù)組和元組數(shù)據(jù)相遇的時(shí)候說(shuō)明當(dāng)前頁(yè)已滿轨蛤。
**Log-Structured（日志結(jié)構(gòu)）：**數(shù)據(jù)庫(kù)存儲(chǔ)日志代替存儲(chǔ)數(shù)據(jù)
存儲(chǔ)數(shù)據(jù)庫(kù)如何被修改的記錄（插入蜜宪，更新，刪除）祥山。
為了讀取記錄圃验，數(shù)據(jù)庫(kù)需要從前往后掃描日志文件去重建元組。
寫入速度快缝呕，讀取速度非常慢澳窑。
在僅追加的情況下效果非常好斧散，因?yàn)閿?shù)據(jù)庫(kù)不會(huì)回滾和更新數(shù)據(jù)。
為了避免讀取過(guò)慢摊聋，數(shù)據(jù)庫(kù)可以創(chuàng)建索引并跳到日志中特定的位置鸡捐。它可以周期性的壓縮日志。（如果有一個(gè)元組被更新了麻裁，我們可以只存儲(chǔ)插入一個(gè)元組箍镜。）但壓縮的問(wèn)題會(huì)導(dǎo)致數(shù)據(jù)庫(kù)的寫放大。（他會(huì)一遍一遍的重寫相同的數(shù)據(jù)煎源。）
八色迂、元組布局
一個(gè)元組的本質(zhì)是一連串的字節(jié)。數(shù)據(jù)庫(kù)將這些字節(jié)解釋成屬性類型和相應(yīng)的值手销。
**Tuple Header（元組頭部）：**包含元組的元數(shù)據(jù)
一些關(guān)于數(shù)據(jù)庫(kù)并發(fā)控制的信息（例如哪個(gè)事務(wù)創(chuàng)建/修改這個(gè)元組）脚草。
標(biāo)記NULL的位圖（bitmap）。
注意原献，數(shù)據(jù)庫(kù)不需要在這里存儲(chǔ)數(shù)據(jù)庫(kù)模式的元數(shù)據(jù)馏慨。
**Tuple Data（元組數(shù)據(jù)）：**每個(gè)屬性真實(shí)的數(shù)據(jù)
屬性通常按照你創(chuàng)建表的時(shí)候的順序存儲(chǔ)。
大多數(shù)數(shù)據(jù)庫(kù)不允許一個(gè)元組超過(guò)頁(yè)的大小姑隅。
Unique Identifier（唯一標(biāo)識(shí)）：
在數(shù)據(jù)庫(kù)中的每個(gè)頁(yè)都被賦予一個(gè)唯一的標(biāo)識(shí)写隶。
最常見的表示：頁(yè)id + (偏移或槽號(hào))。
應(yīng)用程序不能依賴這些id來(lái)做任何事讲仰。
**Denormalized Tuple Data（規(guī)范化的元組數(shù)據(jù)）：**如果2個(gè)表是相關(guān)聯(lián)的慕趴，數(shù)據(jù)庫(kù)可以預(yù)先連接他們，這2個(gè)表會(huì)存在相同的頁(yè)中鄙陡。這樣做可以讓數(shù)據(jù)庫(kù)只加載1個(gè)頁(yè)而不是加載2個(gè)單獨(dú)的頁(yè)冕房，從而大大提高速度。然而趁矾，它將會(huì)導(dǎo)致更新操作的代價(jià)非常大因?yàn)閿?shù)據(jù)庫(kù)對(duì)每個(gè)元組需要更多的空間耙册。
04 數(shù)據(jù)庫(kù)存儲(chǔ)二
一、數(shù)據(jù)表示
元組里的數(shù)據(jù)本質(zhì)上就是字節(jié)數(shù)組毫捣，DBMS知道如何去解釋這些字節(jié)以得到真正的屬性值详拙。數(shù)據(jù)表示模式是DBMS如何通過(guò)字節(jié)去存儲(chǔ)值。
有5種高層數(shù)據(jù)類型可以存儲(chǔ)在元組中：整數(shù)蔓同、浮點(diǎn)數(shù)饶辙、固定精度數(shù)字、變長(zhǎng)數(shù)據(jù)斑粱、日期/時(shí)間弃揽。
Integers（整數(shù)）
大多數(shù)DBMS使用IEEE-754標(biāo)準(zhǔn)的C/C++類型去編碼整數(shù)，這些值是定長(zhǎng)的。
例子：INTEGER, BIGINT, SMALLINT, TINYINT
Variable Precision Numbers（浮點(diǎn)數(shù)）
這些不精確的矿微、精度變化的數(shù)字（浮點(diǎn)數(shù)）使用IEEE-754標(biāo)準(zhǔn)的C/C++類型去編碼痕慢，這些值也是定長(zhǎng)的。
操作浮點(diǎn)數(shù)的速度比操作固定精度的數(shù)字的速度要快冷冗，因?yàn)镃PU可以直接對(duì)浮點(diǎn)數(shù)直接進(jìn)行操作。然而惑艇，由于數(shù)字表示是不精確的蒿辙，所以在計(jì)算的時(shí)候會(huì)出現(xiàn)誤差。
例子：FLOAT, REAL
Fixed-Point Precision Numbers（固定精度數(shù)字滨巴，定點(diǎn)數(shù)）
這些是具有任意精度和小數(shù)位數(shù)的數(shù)字類型思灌。它們通常以精確的，可變長(zhǎng)度的二進(jìn)制表示（像字符串一樣）存儲(chǔ)恭取，另外還會(huì)存儲(chǔ)元數(shù)據(jù)泰偿，這些元數(shù)據(jù)告訴系統(tǒng)數(shù)據(jù)的長(zhǎng)度和小數(shù)點(diǎn)的位置。
當(dāng)數(shù)據(jù)精確性要求很高的時(shí)候可以使用這種類型蜈垮，但DBMS會(huì)花費(fèi)更高的代價(jià)去進(jìn)行計(jì)算蝉仇。
例子：NUMERIC, DECIMAL
Variable-Length Data（變長(zhǎng)數(shù)據(jù)）
他們表示任意長(zhǎng)度的數(shù)據(jù)類型膀懈，他們通常在頭部存儲(chǔ)字符串的長(zhǎng)度，以便跳轉(zhuǎn)到下一個(gè)值，同時(shí)可能還包含數(shù)據(jù)的校驗(yàn)和葫松。
大多數(shù)DBMS不允許一個(gè)元組大小超過(guò)單個(gè)頁(yè)大小。有些則將數(shù)據(jù)存儲(chǔ)在一個(gè)特別的”溢出“頁(yè)上毛好，并在元組上存儲(chǔ)這個(gè)頁(yè)的引用信息魄幕。
也有一些系統(tǒng)會(huì)存儲(chǔ)大數(shù)據(jù)在額外的文件上，并在元組中記錄文件指針偶妖。例如姜凄，如果數(shù)據(jù)庫(kù)存儲(chǔ)圖片信息，DBMS會(huì)直接將圖片存儲(chǔ)在額外的文件中趾访，而不是讓它們?cè)跀?shù)據(jù)庫(kù)中占用大量空間态秧。這樣做的缺點(diǎn)是DBMS無(wú)法操縱這個(gè)文件的內(nèi)容，因此沒有持久性和事務(wù)的保證扼鞋。
例子：VARCHAR, VARBINARY, TEXT, BLOB
Dates and Times（日期和時(shí)間）
日期/時(shí)間的表示因系統(tǒng)的不同而不同屿聋。從unix時(shí)代開始，時(shí)間通常表示為單位時(shí)間（微/毫）秒（時(shí)間戳）藏鹊。
例子：TIME, DATE, TIMESTAMP
System Catalogs（系統(tǒng)目錄）
為了讓DBMS解析元組润讥，它需要維護(hù)一個(gè)內(nèi)部的目錄去告訴數(shù)據(jù)庫(kù)的一些元信息。元信息包含數(shù)據(jù)庫(kù)擁有哪些表和列以及他們的類型和值的順序等信息盘寡。
大多數(shù)DBMS以表的形式在內(nèi)部存儲(chǔ)他們的目錄楚殿，他們使用特殊的代碼”引導(dǎo)“這些目錄表。
二、工作類型
數(shù)據(jù)庫(kù)系統(tǒng)有許多不同的工作類型脆粥，工作類型指的是系統(tǒng)處理的請(qǐng)求的一般類型砌溺。此處介紹2個(gè)類型：在線事務(wù)處理（OLTP），在線分析處理（OLAP）变隔。
OLTP: Online Transaction Processing（在線事務(wù)處理）
OLTP工作類型的特點(diǎn)是快速规伐、短時(shí)間運(yùn)行的操作，一次操作單個(gè)實(shí)體的簡(jiǎn)單查詢和重復(fù)查詢匣缘。
OLTP工作類型的一個(gè)例子是Amazon storefront猖闪。用戶可以添加商品到購(gòu)物車，可以下單購(gòu)買肌厨，但是這些操作只影響一個(gè)賬戶培慌。
OLAP: Online Analytical Processing（在線分析處理）
OLAP工作類型的特點(diǎn)是長(zhǎng)時(shí)間、復(fù)雜的查詢柑爸，對(duì)數(shù)據(jù)庫(kù)大量數(shù)據(jù)的讀取吵护。在OLAP工作類型中，數(shù)據(jù)庫(kù)系統(tǒng)專注于分析表鳍，并從OLTP數(shù)據(jù)庫(kù)中獲取新數(shù)據(jù)（一般為同步鏈路）馅而。
OLAP工作類型的一個(gè)例子是Amazon對(duì)某些地理位置計(jì)算一個(gè)月內(nèi)購(gòu)買最多的5件商品。
HTAP: Hybrid Transaction + Analytical Processing（混合事務(wù)分析處理）
最近流行的一種新型工作類型是HTAP譬圣，它類似于在同一個(gè)數(shù)據(jù)庫(kù)上同時(shí)執(zhí)行OLTP和OLAP的組合用爪。
三、存儲(chǔ)模型
在頁(yè)中存儲(chǔ)元組有很多種方式胁镐，到目前為止偎血，我們假設(shè)n維存儲(chǔ)模型。
N-Ary Storage Model（NSM n維存儲(chǔ)模型）
在n維存儲(chǔ)模型中盯漂，DBMS將一個(gè)元組的所有屬性連續(xù)的存儲(chǔ)在單個(gè)頁(yè)中颇玷，所以NSM又稱為“行存”。這種方法是OLTP工作類型的理想選擇就缆，因?yàn)樵贠LTP場(chǎng)景下帖渠，數(shù)據(jù)是大量插入的，事務(wù)只操作單一的實(shí)體竭宰。DBMS只需要單次獲取就能獲取一個(gè)元組的所有屬性空郊。
優(yōu)點(diǎn)：
快速插入、更新和刪除切揭；對(duì)需要整個(gè)元組的查詢友好狞甚。
缺點(diǎn)：
對(duì)大范圍的掃描和查找一部分屬性不友好，因?yàn)樵诓樵冎锌赡軙?huì)獲取不必要的數(shù)據(jù)來(lái)污染緩沖池廓旬。
Decomposition Storage Model（DSM 分解存儲(chǔ)模型）
在分解存儲(chǔ)模型中哼审，DBMS將一個(gè)單獨(dú)的屬性（列）連續(xù)的存在一個(gè)塊中。因此，這也被稱為“列存”涩盾。該模型非常適合許多具有只讀查詢的OLAP工作類型十气，OLAP經(jīng)常對(duì)一部分屬性進(jìn)行大范圍掃描。
優(yōu)點(diǎn)：
減少查詢過(guò)程中浪費(fèi)的數(shù)據(jù)春霍，因?yàn)镈BMS只讀取查詢所需的數(shù)據(jù)（制度去查詢所需的屬性）砸西。
由于對(duì)同一屬性的所有值連續(xù)存儲(chǔ)，因此可以獲得更好的壓縮性能（或使用特定的壓縮）址儒。
缺點(diǎn)：
由于每個(gè)元組被存在不同的地方芹枷，因此對(duì)文件的點(diǎn)查、插入离福、更新和刪除不友好杖狼。
為了將列存的元組組合回去炼蛤，一般有2種常見的方法：
大多數(shù)使用的方法是*固定長(zhǎng)度的偏移*妖爷。假設(shè)每個(gè)屬性都是固定長(zhǎng)度的，DBMS可以計(jì)算出每個(gè)元組中每個(gè)屬性的偏移理朋，然后當(dāng)想要一個(gè)特定元組的屬性的時(shí)候絮识，它知道如何去跳轉(zhuǎn)到某個(gè)文件某個(gè)位置。為了容納可變長(zhǎng)度的字段嗽上，系統(tǒng)可以填充字段來(lái)達(dá)到相同長(zhǎng)度或者使用固定長(zhǎng)度的字典來(lái)映射值（將超出長(zhǎng)度的值存到另外的文件中并用字典記錄偏移）次舌。
另一個(gè)小眾的方式是使用*嵌入式元組id*。對(duì)每個(gè)在列中的屬性兽愤，DBMS同時(shí)存儲(chǔ)一個(gè)元組id（例如主鍵）彼念。系統(tǒng)會(huì)存儲(chǔ)一個(gè)映射告訴如何找到每個(gè)屬性id所對(duì)應(yīng)的位置。但這個(gè)方法會(huì)浪費(fèi)很多的存儲(chǔ)空間浅萧，因?yàn)槊總€(gè)屬性都會(huì)存儲(chǔ)一個(gè)元組id逐沙。
05 緩沖池
一、簡(jiǎn)介
DBMS 的磁盤管理模塊主要解決兩個(gè)問(wèn)題：
1.如何使用磁盤文件來(lái)表示數(shù)據(jù)庫(kù)的數(shù)據(jù)（元數(shù)據(jù)洼畅、索引吩案、數(shù)據(jù)表等）
2.如何管理數(shù)據(jù)在內(nèi)存與磁盤之間的移動(dòng)：在大多數(shù)情況下，數(shù)據(jù)不能直接在磁盤上操作帝簇，任何數(shù)據(jù)庫(kù)都必須能夠有效地將其磁盤上以文件形式表示的數(shù)據(jù)移動(dòng)到內(nèi)存中徘郭，以便能夠使用。
管理數(shù)據(jù)在內(nèi)存與磁盤之間的移動(dòng)又分為兩個(gè)策略：
空間控制（Spatial Control）：通過(guò)決定將 pages 寫到磁盤的哪個(gè)位置丧肴，使得常常一起使用的 pages 能離得更近残揉，從而提高 I/O 效率。
時(shí)間控制（Temporal Control）：通過(guò)決定何時(shí)將 pages 讀入內(nèi)存芋浮，寫回磁盤冲甘，使得讀寫的次數(shù)最小，從而提高 I/O 效率。
局部性原理：
時(shí)間局部性：程序中的一條指令一旦執(zhí)行江醇，不久后改指令還可能再次被執(zhí)行濒憋。產(chǎn)生時(shí)間局部性的原因是程序中存在大量的循環(huán)操作。?
空間局部性：一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元陶夜，在不久后凛驮，其附近的存儲(chǔ)單元也會(huì)被訪問(wèn)。因?yàn)橹噶畹捻樞蛲ǔＪ琼樞虼鎯?chǔ)条辟、順序執(zhí)行的黔夭。數(shù)據(jù)的存儲(chǔ)也是向量、數(shù)組羽嫡、表等形式
二本姥、鎖? 與? 鎖存器
在討論DBMS如何保護(hù)其內(nèi)部元素時(shí)，我們需要對(duì)鎖和鎖存器進(jìn)行區(qū)分：
鎖：是一個(gè)更高層次的邏輯基元﹐它保護(hù)數(shù)據(jù)庫(kù)的內(nèi)容（如圖元﹑表﹑數(shù)據(jù)庫(kù)）不受其他事務(wù)的影響杭棵。事務(wù)會(huì)在其整個(gè)持續(xù)時(shí)間內(nèi)持有一個(gè)鎖·數(shù)據(jù)庫(kù)系統(tǒng)可以在運(yùn)行查詢時(shí)向用戶展示哪些鎖正在被持有·鎖需要能夠回滾變化·
鎖存器：是一種低級(jí)別的保護(hù)原素﹐DBMS在其內(nèi)部數(shù)據(jù)結(jié)構(gòu)（例如﹐哈希表﹑內(nèi)存區(qū)域)中的宇鍵部分使用·鎖存器只在正在進(jìn)行的操作的時(shí)間內(nèi)保持·鎖存器不需要能夠回滾變化·
三婚惫、緩沖池
緩沖池是一個(gè)從磁盤上讀取頁(yè)面的內(nèi)存緩存·它本質(zhì)上是在數(shù)據(jù)庫(kù)內(nèi)部分配的一個(gè)大的內(nèi)存區(qū)域﹐用來(lái)存儲(chǔ)從磁盤獲取的頁(yè)面。
DBMS 啟動(dòng)時(shí)會(huì)從 OS 申請(qǐng)一片內(nèi)存區(qū)域魂爪，即 Buffer Pool先舷，并將這塊區(qū)域劃分成大小相同的 pages，為了與 disk pages 區(qū)別滓侍，通常稱為 frames蒋川，當(dāng) DBMS 請(qǐng)求一個(gè) disk page 時(shí)，它首先需要被復(fù)制到 Buffer Pool 的一個(gè) frame 中撩笆，如下圖所示：
緩沖池的內(nèi)存區(qū)域被組織成一個(gè)固定大小的頁(yè)面陣列·每個(gè)數(shù)組條目被稱為一個(gè)框架捺球。當(dāng)DBMS請(qǐng)求一個(gè)頁(yè)面時(shí)﹐一個(gè)精確的副本被放置到緩沖池的一個(gè)框架中·然后﹐當(dāng)一個(gè)頁(yè)面被請(qǐng)求時(shí)﹐數(shù)據(jù)庫(kù)系統(tǒng)可以首先搜索緩沖池·如果沒有找到該頁(yè)﹐那么系統(tǒng)就會(huì)從磁盤上獲取該頁(yè)的副本·同時(shí) DBMS 會(huì)維護(hù)一個(gè) page table，負(fù)責(zé)記錄每個(gè) page 在內(nèi)存中的位置夕冲，以及是否被寫過(guò)（Dirty Flag）氮兵，是否被引用或引用計(jì)數(shù)（Pin/Reference Counter）等元信息，如下圖所示：
當(dāng) page table 中的某 page 被引用時(shí)耘擂，會(huì)記錄引用數(shù)（pin/reference）胆剧，表示該 page 正在被使用，空間不夠時(shí)不應(yīng)該被移除醉冤；當(dāng)被請(qǐng)求的 page 不在 page table 中時(shí)秩霍，DBMS 會(huì)先申請(qǐng)一個(gè) latch（lock 的別名），表示該 entry 被占用蚁阳，然后從 disk 中讀取相關(guān) page 到 buffer pool铃绒，釋放 latch。以上兩種過(guò)程如下圖所示：
1.緩沖池元數(shù)據(jù)
緩沖池必須保持某些元數(shù)據(jù)﹐以便有效和正確地使用螺捐。
首先颠悬，頁(yè)表是一個(gè)內(nèi)存中的哈希表矮燎，用于跟蹤當(dāng)前內(nèi)存中的頁(yè)面·它將頁(yè)面ID映射到緩沖池中的框架位置。由于緩沖池中的頁(yè)面順序不一定反映磁盤上的順序﹐這個(gè)額外的中介層允許識(shí)別緩沖池中的頁(yè)面位置◎注意赔癌，頁(yè)面表不能與頁(yè)面目錄混淆诞外，后者是從頁(yè)面ID到數(shù)據(jù)庫(kù)文件中的頁(yè)面位置的映射·
頁(yè)表還維護(hù)著每頁(yè)的額外元數(shù)據(jù)﹐一個(gè)臟標(biāo)志和一個(gè)引腳/參考計(jì)數(shù)器·
每當(dāng)一個(gè)線程修改了一個(gè)頁(yè)面﹐就會(huì)設(shè)置dirty-flag。這表明存儲(chǔ)管理程序必須將該頁(yè)寫回磁盤灾票。Pin/reference
Counier跟蹤當(dāng)前訪問(wèn)該頁(yè)面的線程數(shù)量（無(wú)論是讀取還是修改）·一個(gè)線程在訪問(wèn)該頁(yè)之前必須增加該計(jì)數(shù)器峡谊。如果一個(gè)頁(yè)面的計(jì)數(shù)大于0，那么存儲(chǔ)管理器就不允許將該頁(yè)面從內(nèi)存中驅(qū)逐出去刊苍。
2.內(nèi)存分配策略
數(shù)據(jù)庫(kù)中的內(nèi)存是根據(jù)兩個(gè)策略分配給緩沖池的既们。
全局策略處理DBMS應(yīng)該做出的決定﹐以有利于正在執(zhí)行的整個(gè)工作負(fù)載·它考慮所有活動(dòng)的事務(wù)﹐以找到分配內(nèi)存的最佳決策。
另一種方法是本地策略做出決定正什，使單個(gè)查詢或事務(wù)運(yùn)行得更快﹐即使它對(duì)整個(gè)工作負(fù)載沒有好處·本地策略將框架分配給特定事務(wù)﹐而不考慮并發(fā)事務(wù)的行為啥纸。
四、緩沖池優(yōu)化：適應(yīng)應(yīng)用程序的工作負(fù)荷
1.多個(gè)緩沖池
DBMS可以為不同的目的維護(hù)多個(gè)緩沖池（即每個(gè)數(shù)據(jù)庫(kù)緩沖池﹑每個(gè)頁(yè)面類型的緩沖池）·然后﹐每個(gè)緩沖池可以采用為其內(nèi)部存儲(chǔ)的數(shù)據(jù)定制的本地策略·這種方法可以幫助減少鎖存器的爭(zhēng)用﹐并提高定位性
將所需頁(yè)面映射到緩沖池的兩種方法是對(duì)象ID和散列婴氮。
對(duì)象標(biāo)識(shí)涉及到擴(kuò)展記錄標(biāo)識(shí)﹐以包括矣于每個(gè)緩沖池管理哪些數(shù)據(jù)庫(kù)對(duì)象的元數(shù)據(jù)·然后通過(guò)對(duì)象標(biāo)識(shí)符斯棒，可以維護(hù)對(duì)象與特定緩沖池之間的映射尖系。
另一種方法是散列法莹妒，DBMS對(duì)頁(yè)面ID進(jìn)行散列以選擇訪問(wèn)哪個(gè)緩沖池名船。
2.預(yù)取
DBMS也可以通過(guò)基于查詢計(jì)劃的預(yù)取頁(yè)面來(lái)進(jìn)行優(yōu)化·然后﹐當(dāng)?shù)谝唤M頁(yè)面被處理時(shí)﹐第二組可以被預(yù)取到緩沖池中绰上。這種方法是DBMS在連續(xù)訪問(wèn)許多頁(yè)面時(shí)常用的旨怠。
3.掃描共享
查詢游標(biāo)可以重復(fù)使用從存儲(chǔ)或操作者計(jì)算中獲取的數(shù)據(jù)·這允許多個(gè)查詢附加到一個(gè)掃描表的游標(biāo)上。如果一個(gè)查詢開始掃描﹐如果已經(jīng)有一個(gè)在做這個(gè)﹐那么DBMS將附加到第二個(gè)查詢的游標(biāo)·DBMS跟蹤第二個(gè)查詢與第一個(gè)查詢的連接位置﹐這樣它就可以在到達(dá)數(shù)據(jù)結(jié)構(gòu)的末端時(shí)完成掃描蜈块。
4.緩沖池旁路
順序掃描操作者不會(huì)將獲取的頁(yè)面存儲(chǔ)在緩沖池中以避免開銷·相反﹐內(nèi)存是運(yùn)行中的查詢的局部·如果操作者需要在
磁盤上讀取連續(xù)的大序列頁(yè)面﹐這種方法很有效·緩沖池旁路也可用于臨時(shí)數(shù)據(jù)（排序·連接)鉴腻。
五、操作系統(tǒng)頁(yè)面緩存
大多數(shù)磁盤操作是通過(guò)操作系統(tǒng)的API進(jìn)行的·除非被明確告知﹐操作系統(tǒng)會(huì)維護(hù)自己的文件系統(tǒng)緩存百揭。大多數(shù)DBMS使用直接IO來(lái)繞過(guò)操作系統(tǒng)的緩存﹐以避免頁(yè)面的冗余拷貝和不得不管理不同的驅(qū)逐策略爽哎。Postgres是一個(gè)使用操作系統(tǒng)頁(yè)面緩存的數(shù)據(jù)庫(kù)系統(tǒng)的例子。
六器一、緩沖區(qū)替代政策
當(dāng)DBMS需要釋放一個(gè)框架來(lái)為一個(gè)新的頁(yè)面騰出空間時(shí)﹐它必須決定從緩沖池中驅(qū)逐哪個(gè)頁(yè)面课锌。替換策略是DBMS實(shí)現(xiàn)的一種算法﹐當(dāng)它需要空間時(shí)﹐它決定將哪些頁(yè)面從緩沖池中驅(qū)逐。
替換策略的實(shí)施目標(biāo)是提高正確性﹑準(zhǔn)確性·速度和元數(shù)據(jù)的開銷祈秕。
1.最近使用最少的(LRU) 渺贤。
最近最少使用的替換策略維護(hù)著每個(gè)頁(yè)面最后被訪問(wèn)的時(shí)間戳·這個(gè)時(shí)間戳可以存儲(chǔ)在一個(gè)單獨(dú)的數(shù)據(jù)結(jié)構(gòu)中，比如一個(gè)隊(duì)列﹐以便進(jìn)行排序和提高效率·DBMS選擇驅(qū)逐具有最古老時(shí)間戳的頁(yè)面·此外﹐頁(yè)面以排序的方式保存请毛，以減少驅(qū)逐時(shí)的排序時(shí)間志鞍。
2.鐘
CLOCK策略是LRU的一個(gè)近似值﹐不需要每頁(yè)有單獨(dú)的時(shí)間戳·在CLOCK策略中，每個(gè)頁(yè)面被賦予一個(gè)參考位方仿。當(dāng)一個(gè)頁(yè)面被訪問(wèn)時(shí)﹐設(shè)置為1固棚。
為了形象地說(shuō)明這一點(diǎn)﹐可以用"時(shí)鐘指針
"在一個(gè)圓形緩沖區(qū)中組織頁(yè)面·在清掃時(shí)檢查一個(gè)頁(yè)面的位是否被設(shè)置為1统翩，如果是，則設(shè)置為0此洲，如果不是厂汗，則驅(qū)逐它·通過(guò)這種方式﹐時(shí)鐘指針在驅(qū)逐之間記住了位置。
3.替代品
LRU和CLOCK替換策略有很多問(wèn)題呜师。
也就是說(shuō)﹐LRU和CLOCK很容易受到順序泛濫的影響面徽，即緩沖池的內(nèi)容由于順序掃描而被破壞·由于順序掃描會(huì)讀取每一頁(yè)﹐所以讀取的頁(yè)面的時(shí)間戳可能并不反映我們真正想要的頁(yè)面·換句話說(shuō)﹐最近使用的頁(yè)面實(shí)際上是最不需要的頁(yè)面。
有三種解決萬(wàn)案可以解決LRU和CLOCK策略的缺點(diǎn)匣掸。一種解決方案是LRU-K趟紊，它以時(shí)間戳的形式跟蹤最近的K次引用的歷史﹐并計(jì)算出后續(xù)訪問(wèn)的間隔時(shí)間·這個(gè)歷史記錄被用來(lái)預(yù)測(cè)一個(gè)頁(yè)面下次被訪問(wèn)的時(shí)間。
另一個(gè)優(yōu)化是每個(gè)查詢的定位碰酝。DBMS在每個(gè)事務(wù)/查詢的基礎(chǔ)上選擇哪些頁(yè)面要被驅(qū)逐·這使得每次查詢對(duì)緩沖池的污染最小化霎匈。
最后，優(yōu)先級(jí)提示允許事務(wù)根據(jù)查詢執(zhí)行期間每個(gè)頁(yè)面的上下文告訴緩沖池頁(yè)面是否重要送爸。
4.臟頁(yè)面
有兩種方法來(lái)處理有臟位的頁(yè)面·最快的方法是丟棄緩沖池中任何不臟的頁(yè)面·一個(gè)較慢的方法是將臟頁(yè)寫回磁盤﹐以確保其變化被持久化铛嘱。
這兩種方法說(shuō)明了快速驅(qū)逐與臟寫頁(yè)之間的權(quán)衡﹐臟寫頁(yè)在未來(lái)不會(huì)被再次讀取。
避免不必要地寫出頁(yè)的問(wèn)題的一個(gè)方法是后臺(tái)寫入袭厂。通過(guò)后臺(tái)寫入﹐DBMS可以周期性地走過(guò)頁(yè)表并將臟頁(yè)寫入磁盤墨吓。當(dāng)一個(gè)臟頁(yè)被安全寫入時(shí)﹐DBMS可以驅(qū)逐該頁(yè)﹐或者直接取消臟頁(yè)標(biāo)志。
七纹磺、其他內(nèi)存池
除了圖元和索引之外﹐DBMS還需要內(nèi)存帖烘。這些其他的內(nèi)存池可能并不總是由磁盤支持，這取決于實(shí)現(xiàn)橄杨。
·分揀+連接緩沖器
·查詢緩存
·維護(hù)緩沖區(qū)
·日志緩沖區(qū)
·詞典緩存
07 哈希表
為了支持 DBMS 更高效地從 pages 中讀取數(shù)據(jù)秘症，DBMS 的設(shè)計(jì)者需要靈活運(yùn)用一些數(shù)據(jù)結(jié)構(gòu)及算法，其中對(duì)于 DBMS 最重要的兩個(gè)是：Hash Tables式矫、Trees
它們可能被用在 DBMS 的多個(gè)地方乡摹，包括：
Internal Meta-data????????內(nèi)部元數(shù)據(jù)
Core Data Storage????????核心數(shù)據(jù)存儲(chǔ)
Temporary Data Structures????????臨時(shí)數(shù)據(jù)結(jié)構(gòu)
Table Indexes????????表索引
在做相關(guān)的設(shè)計(jì)決定時(shí)，通常需要考慮兩個(gè)因素：
Data Organization：如何將這些數(shù)據(jù)結(jié)構(gòu)合理地放入 memory/pages 中采转，以及為了支持更高效的訪問(wèn)聪廉，應(yīng)當(dāng)存儲(chǔ)哪些信息
Concurrency：如何支持?jǐn)?shù)據(jù)的并發(fā)訪問(wèn)
一、數(shù)據(jù)結(jié)構(gòu)
DBMS為系統(tǒng)內(nèi)部的許多不同部分使用各種數(shù)據(jù)結(jié)構(gòu)故慈。例如：
·內(nèi)部元數(shù)據(jù)板熊。這是對(duì)數(shù)據(jù)庫(kù)和系統(tǒng)狀態(tài)信息進(jìn)行跟蹤的數(shù)據(jù)。例如∶頁(yè)面表格﹑頁(yè)面目錄
·核心數(shù)據(jù)存儲(chǔ)惯悠。數(shù)據(jù)結(jié)構(gòu)被用來(lái)作為數(shù)據(jù)庫(kù)中圖元的基礎(chǔ)存儲(chǔ)邻邮。
·臨時(shí)數(shù)據(jù)結(jié)構(gòu)。DBMS可以在處理查詢的過(guò)程中即時(shí)建立數(shù)據(jù)結(jié)構(gòu)﹐以加快執(zhí)行速度（例如克婶，用于連接的哈希表）筒严。
·表索引丹泉。輔助數(shù)據(jù)結(jié)構(gòu)可以用來(lái)使查找特定的圖元更加容易·在為DBMS實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)時(shí)﹐有兩個(gè)主要的設(shè)計(jì)決策需要考慮：
1.數(shù)據(jù)組織·我們需要弄清楚如何布局內(nèi)存﹐以及在數(shù)據(jù)結(jié)構(gòu)內(nèi)存儲(chǔ)哪些信息﹐以支持高效的訪問(wèn)。
2.并發(fā)性·我們還需要考慮如何使多個(gè)線程訪問(wèn)數(shù)據(jù)結(jié)構(gòu)鸭蛙，而不造成問(wèn)題摹恨。
二、哈希表
哈希表實(shí)現(xiàn)了一個(gè)分聯(lián)數(shù)組的抽象數(shù)據(jù)類型﹐將鍵映射到值·它平均提供了O(1)的操作復(fù)雜度(最壞情況下為O(n))和O(n)的存儲(chǔ)復(fù)雜度娶视。請(qǐng)注意﹐即使平均操作復(fù)雜度為O(1)晒哄，也有恒定系數(shù)的優(yōu)化﹐這在現(xiàn)實(shí)世界中是需要考慮的。
一個(gè)哈希表的實(shí)現(xiàn)由兩部分組成：
·哈希函數(shù)（Hash Function）如何將一個(gè)大的密鑰空間映射到一個(gè)較小的領(lǐng)域肪获。它被用來(lái)計(jì)算進(jìn)入一個(gè)桶或槽陣列的索引·我們需要考慮快速執(zhí)行和碰撞率之間的權(quán)衡在一個(gè)極端寝凌，我們有一個(gè)總是返回一個(gè)常數(shù)的哈希函數(shù)（非常快﹐但一切都會(huì)發(fā)生碰撞）孝赫。在另一個(gè)極端较木，我們有一個(gè)"完美"的散列函數(shù)，沒有碰撞青柄，但計(jì)算時(shí)間非常長(zhǎng)О理想的設(shè)計(jì)是介于兩者之間伐债。
·哈希方案（Hashing Scheme）這告訴我們?nèi)绾翁幚砩⒘泻蟮拿荑€碰撞。在這里致开，我們需要考慮分配一個(gè)大的哈希表以減少碰撞和在發(fā)生碰撞時(shí)不得不執(zhí)行額外的指合之間的權(quán)衡峰锁。
1、哈希函數(shù)
由于 DBMS 內(nèi)使用的 Hash Function 并不會(huì)暴露在外双戳，因此沒必要使用加密（cryptographic）哈希函數(shù)虹蒋，我們希望它速度越快，collision rate 越低越好拣技。
散列函數(shù)接受任何鍵作為其輸人千诬。然后它返回該鍵的整數(shù)表示（即"哈希")耍目。該函數(shù)的輸出是確定的(即﹐相同的密鑰應(yīng)該總是產(chǎn)生相同的哈希輸出）膏斤。DBMS不需要使用加密安全的哈希醫(yī)數(shù)（例如SHA-256)，因?yàn)槲覀儾恍枰獡?dān)心保護(hù)密鑰的內(nèi)容·這些哈希函數(shù)主要由DBMS內(nèi)部使用邪驮，因此信息不會(huì)泄露到系統(tǒng)之外莫辨。一般來(lái)說(shuō)﹐我們只尖心哈希函數(shù)的速度和碰撞率。目前最先進(jìn)的哈希函數(shù)是Facebook XXHash3
2毅访、靜態(tài)哈希方案
靜態(tài)散列方案是指散列表的大小是固定的·這意味著如果DBMS在哈希表中的存儲(chǔ)空間用完了﹐那么它就必須從頭開始重建一個(gè)更大的哈希表﹐這非常昂貴·通常﹐新的哈希表是原始哈希表大小的兩倍沮榜。
為了減少浪費(fèi)的比較吹數(shù)﹐避免哈希鍵的碰撞是很重要的·通常情況下﹐我們使用兩倍于預(yù)期元秦?cái)?shù)量的槽位。
以下假設(shè)在現(xiàn)實(shí)中通常是不成立的喻粹。
1．元素的數(shù)量是提前知道的蟆融。
2．keys是獨(dú)一無(wú)二的。
3．存在一個(gè)完美的哈希函數(shù)守呜。
因此型酥，我們需要適當(dāng)?shù)剡x擇散列函數(shù)和散列模式山憨。
2.1 線性探測(cè)
這是最基本的散列方案·它通常也是最快的·它使用數(shù)組槽的循環(huán)緩沖區(qū)·散列函數(shù)將鍵映射到槽。當(dāng)碰撞發(fā)生時(shí)﹐我們線性地搜索相鄰的槽﹐直到找到一個(gè)開放的槽·對(duì)于查找﹐我們可以檢查鍵的哈希值所對(duì)應(yīng)的槽﹐然后線性搜索﹐直到找到所需的條目·如果我們到達(dá)一個(gè)空槽﹐或者我們遍歷了hashtable中的每一個(gè)槽弥喉，那么這個(gè)鍵就不在表中郁竟。請(qǐng)注意﹐這意味著我們必須在槽中同時(shí)存儲(chǔ)鍵和值﹐以便我們可以檢查一個(gè)條目是否是所需的·刪除是比較棘手的·我們必須小心地從槽中刪除條目﹐因?yàn)檫@可能會(huì)阻止未來(lái)的查詢找到被放在現(xiàn)在空槽下面的條目·這個(gè)問(wèn)題有兩個(gè)解決方案。
·最常見的方法是使用"墓碑"由境。我們不刪除這個(gè)條目﹐而是用一個(gè)"墓碑"條目來(lái)代替它棚亩，告訴未來(lái)的查找工作要繼續(xù)掃描虏杰。
·另一個(gè)選擇是在刪除一個(gè)條目后移動(dòng)相鄰的數(shù)據(jù)以填補(bǔ)現(xiàn)在的空槽·然而﹐我們必須注意只移動(dòng)最初被移位的條目讥蟆。這在實(shí)踐中很少實(shí)現(xiàn)。
非唯一鍵：keys 可能出現(xiàn)重復(fù)纺阔，但 value 不同﹐有兩種方法攻询。
·單獨(dú)的鏈接列表О我們不將數(shù)值與鍵一起存儲(chǔ)﹐而是將一個(gè)指針指向一個(gè)單獨(dú)的存儲(chǔ)區(qū)域﹐該區(qū)域包含所有數(shù)值的鏈接列表钧栖。（拉鏈法/鏈地址法）
·冗長(zhǎng)的鍵。更常見的方法是簡(jiǎn)單地在表中多次存儲(chǔ)同一個(gè)鍵·即使我們這樣做﹐所有具有線性探測(cè)功能的東西仍然有效婆翔。
2.2?羅賓漢哈希
這是線性探測(cè)散列的一個(gè)擴(kuò)展﹐為了防止 Linear Probe Hashing 出現(xiàn)連續(xù)區(qū)域?qū)е骂l繁的 probe探測(cè)操作拯杠。基本思路是 “劫富濟(jì)貧”啃奴，即每次比較的時(shí)候潭陪，同時(shí)需要比較每個(gè) key 距離其原本位置的距離（越近越富余，越遠(yuǎn)越貧窮）最蕾，如果遇到一個(gè)已經(jīng)被占用的槽依溯，如果它比自己富余，則可以直接替代它的位置瘟则，然后把它順延到新的位置黎炉。
2.3布谷鳥哈希法
這種方法不是使用單一的哈希表﹐而是用不同的哈希函數(shù)維護(hù)多個(gè)哈希表。這些哈希函數(shù)是相同的算法（如XXHash醋拧、CityHash);它們通過(guò)使用不同的種子值為同一個(gè)密鑰生成不同的哈希值慷嗜。當(dāng)我們插人時(shí)﹐我們檢查每一個(gè)表﹐并選擇一個(gè)有空閑位置的表(如果多個(gè)表都有空閑位置﹐我們可以比較一些東西﹐如負(fù)載系數(shù)﹐或者更常見的是﹐只是選擇一個(gè)隨機(jī)的表)·如果沒有表有空閑的槽﹐我們就選擇（通常是隨機(jī)的）并驅(qū)逐舊條目·然后﹐我們將舊條目重新洗牌到一個(gè)不同的表中。在極少數(shù)情況下丹壕，我們可能會(huì)在一個(gè)循環(huán)中結(jié)束·如果發(fā)生這種情況﹐我們可以用新的哈希函數(shù)種子重建所有的哈希表(不太常見）或者用更大的表重建哈希表(更常見)庆械。
布谷鳥散列保證了O(1)查找和刪除﹐但插入可能更昂貴。
3菌赖、動(dòng)態(tài)哈希方案
靜態(tài)散列方案要求DBMS知道它要存儲(chǔ)的元素的數(shù)量·否則﹐如果需要擴(kuò)大/縮小表的大小﹐它就必須重建表缭乘。
動(dòng)態(tài)散列方案能夠根據(jù)需要調(diào)整散列表的大小﹐而不需要重建整個(gè)表。這些方案以不同的方式執(zhí)行這種大小調(diào)整﹐可以最大限度地提高讀取或?qū)懭搿?/p>
3.1鏈?zhǔn)焦Ｋ惴?/b>
這是最常見的動(dòng)態(tài)散列方案垄惧。DBMS為哈希表中的每個(gè)槽維護(hù)一個(gè)鏈接列表·對(duì)同一個(gè)槽進(jìn)行散列的鍵被簡(jiǎn)單地插入到該槽的鏈接列表中。這么做的好處就是簡(jiǎn)單绰寞，壞處就是最壞的情況下 Hash Table 可能降級(jí)成鏈表到逊，使得操作的時(shí)間復(fù)雜度降格為 O(n) 。
3.2可擴(kuò)展的哈希算法
鏈?zhǔn)缴⒘械母倪M(jìn)版本﹐它將桶拆分﹐而不是讓鏈永遠(yuǎn)增長(zhǎng)·這種方法允許哈希表中的多個(gè)槽位指向同一個(gè)桶鏈滤钱。
重新平衡哈希表的核心思想是在拆分時(shí)移動(dòng)桶的條目﹐并增加檢查的位數(shù)﹐以便在哈希表中找到條目觉壶。這意味著DBMS只需要在分割鏈的桶內(nèi)移動(dòng)數(shù)據(jù)﹔所有其他的桶都不會(huì)被觸動(dòng)。
DBMS維護(hù)著全局和局部的深度位數(shù)﹐這些位數(shù)決定了在槽陣列中尋找桶所需的位數(shù)件缸⊥校·當(dāng)一個(gè)桶滿了﹐DBMS會(huì)分割這個(gè)桶并重新洗牌其元素·如果分割后的水桶的局部深度小于全局深度，那么新的水桶只是被添加到現(xiàn)有的槽陣列中·否則﹐DBMS將槽陣列的大小增加一倍以容納新的槽﹐并增加全局深度計(jì)數(shù)器他炊。
3.3 線性哈希
當(dāng)一個(gè)桶溢出時(shí)﹐這個(gè)方案并不立即分割﹐而是保持一個(gè)分割指針争剿，跟蹤下一個(gè)要分割的桶。無(wú)論這個(gè)指針是否指向一個(gè)溢出的桶﹐DBMS都會(huì)進(jìn)行分割·溢出的標(biāo)準(zhǔn)由實(shí)現(xiàn)者決定痊末。
·當(dāng)任何一個(gè)桶溢出時(shí)﹐通過(guò)添加一個(gè)新的槽條目﹐在指針位置分割該桶﹐并創(chuàng)建一個(gè)新的哈希醫(yī)數(shù)蚕苇。
·如果哈希函數(shù)映射到以前被指針指向的槽﹐則應(yīng)用新的哈希函數(shù)·
·當(dāng)指針到達(dá)最后一個(gè)槽時(shí)﹐刪除原來(lái)的哈希函數(shù)﹐用一個(gè)新的哈希函數(shù)來(lái)代替它没酣。
08 樹狀索引
一忱详、表索引
table index 為提供 DBMS 數(shù)據(jù)查詢的快速索引，它本身存儲(chǔ)著某表某列排序后的數(shù)據(jù)锰瘸，并包含指向相應(yīng) tuple 的指針盒件。DBMS 需要保證表信息與索引信息在邏輯上保持同步蹬碧。用戶可以在 DBMS 中為任意表建立多個(gè)索引，DBMS 的工作是找出執(zhí)行查詢所需的最佳索引炒刁。但索引自身需要占用存儲(chǔ)空間恩沽，因此在索引數(shù)量與索引存儲(chǔ)、維護(hù)成本之間存在權(quán)衡切心。
二飒筑、B+樹
B+ Tree 是一種自平衡樹，它將數(shù)據(jù)有序地存儲(chǔ)绽昏，且在 搜索、順序訪問(wèn)俏脊、插入 以及 刪除 操作的復(fù)雜度上都滿足 O(logn) 全谤，其中 順序訪問(wèn)的最終復(fù)雜度還與所需數(shù)據(jù)總量有關(guān)。
B+ Tree 可以看作是 BST (Binary Search Tree爷贫，二叉查找樹：左小右大) 的衍生結(jié)構(gòu)认然，它的每個(gè)節(jié)點(diǎn)可以有多個(gè) children补憾，這特別契合 disk-oriented database （面向磁盤的數(shù)據(jù)庫(kù)）的數(shù)據(jù)存儲(chǔ)方式，每個(gè) page 存儲(chǔ)一個(gè)節(jié)點(diǎn)卷员，使得樹的結(jié)構(gòu)扁平化盈匾，減少獲取索引給查詢帶來(lái)的 I/O 成本。
B-Tree和B+Tree之間的主要區(qū)別是毕骡，B-Tree在所有節(jié)點(diǎn)中存儲(chǔ)鍵和值削饵，而B+樹只在葉節(jié)點(diǎn)中存儲(chǔ)值。現(xiàn)代B+樹的實(shí)現(xiàn)結(jié)合了其他B-樹變體的特征未巫，例如Blink-樹中使用的兄弟姐妹指針窿撬。
從形式上看，B+樹是一棵M-way搜索樹（其中M代表一個(gè)節(jié)點(diǎn)可以擁有的最大子女?dāng)?shù)）叙凡，具有以下特性劈伴。
?它是完全平衡的（即每個(gè)葉子節(jié)點(diǎn)都處于相同的深度）。
??除根以外的每個(gè)內(nèi)部節(jié)點(diǎn)至少有一半是滿的（M/21 < = 鍵的數(shù)量< = M1）握爷。
? 每個(gè)有k個(gè)鍵的內(nèi)部節(jié)點(diǎn)都有k+1個(gè)非空的子節(jié)點(diǎn)跛璧。
??每個(gè)節(jié)點(diǎn)最多存儲(chǔ) M 個(gè) key，有 M+1 個(gè) children
??除了 root 節(jié)點(diǎn)新啼，所有其它節(jié)點(diǎn)中至少處于半滿狀態(tài)
??B+ Tree 的 leaf nodes 通過(guò)雙向鏈表串聯(lián)赡模，從而為 sequential access 提供更高效的支持
B+Tree中的每個(gè)節(jié)點(diǎn)都包含一個(gè)鍵/值對(duì)數(shù)組。這些對(duì)中的鍵是由索引所基于的屬性派生的师抄。 ?這些值會(huì)根據(jù)一個(gè)節(jié)點(diǎn)是內(nèi)部節(jié)點(diǎn)還是葉子節(jié)點(diǎn)而有所不同漓柑。 ?對(duì)于內(nèi)部節(jié)點(diǎn)，值數(shù)組將包含指向其他節(jié)點(diǎn)的指針叨吮。 ?葉子節(jié)點(diǎn)值的兩種方法是記錄ID和元組數(shù)據(jù)辆布。記錄ID指的是一個(gè)指向元組位置的指針。有元組數(shù)據(jù)的葉子節(jié)點(diǎn)在每個(gè)節(jié)點(diǎn)中存儲(chǔ)元組的實(shí)際內(nèi)容茶鉴。
B+樹代碼
B+ Tree 中的每個(gè) node 都包含一列按 key 排好序的 key/value pairs锋玲，key 就是 table index 對(duì)應(yīng)的 column，value 的取值與 node 類型相關(guān)涵叮，在 inner nodes 和 leaf nodes 中存的內(nèi)容不同惭蹂。
leaf node 的 values 取值在不同數(shù)據(jù)庫(kù)中、不同索引優(yōu)先級(jí)中也不同割粮，但總而言之盾碗，通常有兩種做法：
*Record/Tuple Ids：存儲(chǔ)指向最終 tuple 的指針
*Tuple Data：直接將 tuple data 存在 leaf node 中，但這種方式對(duì)于 Secondary Indexes 不適用舀瓢，因?yàn)?DBMS 只能將 tuple 數(shù)據(jù)存儲(chǔ)到一個(gè) index 中廷雅，否則數(shù)據(jù)的存儲(chǔ)就會(huì)出現(xiàn)冗余，同時(shí)帶來(lái)額外的維護(hù)成本。
此外航缀，leaf node 還需要存儲(chǔ)相鄰 siblings 的地址以及其它一下元信息商架，如下圖所示：
三、B+樹操作
插入
要在B+樹中插入一個(gè)新的條目芥玉，必須沿著樹向下遍歷蛇摸，并使用內(nèi)部節(jié)點(diǎn)來(lái)確定將鑰匙插入哪個(gè)葉子節(jié)點(diǎn)。
1.找到對(duì)應(yīng)的 leaf node灿巧，L
2.將 key/value pair 按順序插入到 L 中
3.如果 L 還有足夠的空間赶袄，操作結(jié)束；如果空間不足砸烦，則需要將 L 分裂成兩個(gè)節(jié)點(diǎn)弃鸦，同時(shí)在 parent node 上新增 entry，若 parent node 也空間不足幢痘，則遞歸地分裂唬格，直到 root node 為止。
刪減
在插入過(guò)程中颜说，當(dāng)樹變得太滿時(shí)购岗，我們偶爾不得不分割葉子，而如果刪除導(dǎo)致樹少于半滿门粪，我們必須進(jìn)行合并喊积，以重新平衡樹。
1.找到正確的葉子L玄妈。
2. 刪除該條目乾吻。
?如果L至少是半滿，操作就完成了拟蜻。
?否則绎签，你可以嘗試重新分配，從兄弟姐妹那里借錢酝锅。
?如果重新分配失敗诡必，則合并L和兄弟姐妹。
3.如果發(fā)生合并搔扁，你必須刪除指向L的父項(xiàng)爸舒。
選擇條件
因?yàn)锽+Tree是按排序的，所以查找有快速的遍歷稿蹲，也不需要整個(gè)鍵扭勉。如果查詢提供了搜索鍵的任何屬性，DBMS可以使用B+Tree索引场绿。這與散列索引不同剖效，散列索引需要搜索鍵中的所有屬性嫉入。
非唯一索引
像散列表一樣焰盗，B+Trees可以通過(guò)重復(fù)鍵或存儲(chǔ)值列表來(lái)處理非唯一的索引璧尸。在重復(fù)鍵的方法中，使用相同的葉子節(jié)點(diǎn)布局熬拒，但重復(fù)的鍵被多次存儲(chǔ)爷光。 ???在值列表方法中，每個(gè)鍵只存儲(chǔ)一次澎粟，并保持一個(gè)唯一值的鏈接列表蛀序。
重復(fù)的key
在B+Tree中，有兩種方法來(lái)重復(fù)鍵活烙。
第一種方法是將記錄ID作為密鑰的一部分徐裸。由于每個(gè)元組的記錄ID是唯一的，這將確保所有的鍵都是可識(shí)別的啸盏。
第二種方法是允許葉子節(jié)點(diǎn)溢出到包含重復(fù)鍵的溢出節(jié)點(diǎn)重贺。雖然沒有多余的信息被存儲(chǔ)，但這種方法的維護(hù)和修改更加復(fù)雜回懦。
集群索引
該表按照主鍵指定的排序順序存儲(chǔ)气笙，作為堆組織或索引組織的存儲(chǔ)。由于一些DBMS總是使用聚類索引怯晕，所以如果一個(gè)表沒有明確的主鍵潜圃，它們會(huì)自動(dòng)做一個(gè)隱藏的行id主鍵，但是其他的DBMS根本不能使用它們舟茶。
堆積聚類
圖元在堆的頁(yè)面中使用聚類索引指定的順序進(jìn)行排序谭期。如果聚類索引的屬性被用來(lái)訪問(wèn)圖元，DBMS可以直接跳到這些頁(yè)面吧凉。
索引掃描頁(yè)面排序
由于直接從非聚類索引中檢索圖元的效率很低隧出，DBMS可以首先找出它所需要的所有圖元，然后根據(jù)它們的頁(yè)面ID進(jìn)行排序客燕。
三鸳劳、B+樹設(shè)計(jì)的選擇
3.1節(jié)點(diǎn)大小
根據(jù)存儲(chǔ)介質(zhì)的不同，我們可能喜歡更大或更小的節(jié)點(diǎn)尺寸也搓。例如赏廓，存儲(chǔ)在硬盤上的節(jié)點(diǎn)通常是以兆字節(jié)為單位的，以減少尋找數(shù)據(jù)所需的次數(shù)傍妒，并將昂貴的磁盤讀取分?jǐn)偟揭淮髩K數(shù)據(jù)上幔摸，而內(nèi)存數(shù)據(jù)庫(kù)可能使用小到512字節(jié)的頁(yè)面大小，以便將整個(gè)頁(yè)面放入CPU緩存颤练，并減少數(shù)據(jù)碎片既忆。 ?這種選擇也取決于工作負(fù)載的類型，如點(diǎn)查詢會(huì)喜歡盡可能小的頁(yè)面，以減少不必要的額外信息的加載量患雇，而大型順序掃描可能更喜歡大的頁(yè)面跃脊，以減少它需要做的取數(shù)。
3.2合并閾值
雖然B+Trees有一條規(guī)則苛吱，即在刪除后合并溢出的節(jié)點(diǎn)酪术，但有時(shí)暫時(shí)違反該規(guī)則以減少刪除操作的數(shù)量可能是有益的。例如翠储，急于合并可能會(huì)導(dǎo)致激動(dòng)绘雁，大量連續(xù)的刪除和插入操作會(huì)導(dǎo)致不斷的分裂和合并。它還允許分批合并援所，即一次發(fā)生多個(gè)合并操作庐舟，減少在樹上進(jìn)行昂貴的寫鎖存的時(shí)間。
3.3可變長(zhǎng)度的key
目前我們只討論了具有固定長(zhǎng)度鍵的B+Trees住拭。然而挪略，我們可能也想支持可變長(zhǎng)度的鍵，比如說(shuō)一個(gè)大鍵的小子集導(dǎo)致大量空間浪費(fèi)的情況废酷。對(duì)此有幾種方法瘟檩。
1.指示器
我們可以不直接存儲(chǔ)鍵，而只是存儲(chǔ)一個(gè)指向鍵的指針澈蟆。由于必須為每個(gè)鍵追尋一個(gè)指針的低效率墨辛，在生產(chǎn)中使用這種方法的唯一地方是嵌入式設(shè)備，其微小的寄存器和緩存可能會(huì)從這種空間的節(jié)省中受益
2.可變長(zhǎng)度的節(jié)點(diǎn)
我們也可以像平常一樣存儲(chǔ)密鑰趴俘，并允許可變長(zhǎng)度的節(jié)點(diǎn)睹簇。這是不可行的，而且由于處理可變長(zhǎng)度的節(jié)點(diǎn)有很大的內(nèi)存管理開銷寥闪，所以基本上沒有使用太惠。
3.填充物
我們可以不改變鑰匙的大小，而是將每個(gè)鑰匙的大小設(shè)置為最大鑰匙的大小疲憋，并將所有較短的鑰匙墊出凿渊。在大多數(shù)情況下，這是對(duì)內(nèi)存的巨大浪費(fèi)缚柳，所以你也不會(huì)看到有人使用這種方法埃脏。
4.關(guān)鍵地圖/方向
幾乎每個(gè)人都在使用的方法是用一個(gè)索引來(lái)代替鍵值對(duì)在一個(gè)單獨(dú)的字典中的鍵值。這可以大大節(jié)省空間秋忙，并有可能縮短點(diǎn)查詢（因?yàn)樗饕赶虻逆I值對(duì)與葉子節(jié)點(diǎn)指向的鍵值對(duì)完全相同）彩掐。由于字典索引值的大小較小，有足夠的空間將每個(gè)鍵的前綴放在索引旁邊灰追，可能允許一些索引搜索和葉子掃描堵幽，甚至不必追逐指針（如果前綴與搜索鍵有任何不同）狗超。
3.4節(jié)點(diǎn)內(nèi)搜索
一旦我們到達(dá)一個(gè)節(jié)點(diǎn)，我們?nèi)匀恍枰谠摴?jié)點(diǎn)內(nèi)進(jìn)行搜索（要么從內(nèi)部節(jié)點(diǎn)找到下一個(gè)節(jié)點(diǎn)朴下，要么在葉子節(jié)點(diǎn)中找到我們的鍵值）努咐。雖然這相對(duì)簡(jiǎn)單，但仍有一些權(quán)衡需要考慮桐猬。
1.線性
最簡(jiǎn)單的解決方案是直接掃描節(jié)點(diǎn)中的每個(gè)鍵溃肪，直到我們找到我們的鍵。一方面音五，我們不必?fù)?dān)心對(duì)鍵進(jìn)行排序惫撰，使插入和刪除變得更快。另一方面躺涝，這也是相對(duì)低效的厨钻，每次搜索的復(fù)雜度為O(n)。這可以使用SIMD（或同等）指令進(jìn)行矢量處理坚嗜。
2.二進(jìn)制
一個(gè)更有效的搜索方案是保持每個(gè)節(jié)點(diǎn)的排序夯膀，并使用二進(jìn)制搜索來(lái)尋找鑰匙。這就像跳到一個(gè)節(jié)點(diǎn)的中間苍蔬，根據(jù)鍵的比較诱建，向左或向右轉(zhuǎn)動(dòng)一樣簡(jiǎn)單。這種方式的搜索效率更高碟绑，因?yàn)檫@種方法每次搜索的復(fù)雜度只有O(ln(n))俺猿。然而，插入變得更加昂貴格仲，因?yàn)槲覀儽仨毦S護(hù)每個(gè)節(jié)點(diǎn)的排序押袍。
3.內(nèi)插法
最后，在某些情況下凯肋，我們可能會(huì)利用插值法來(lái)尋找鑰匙谊惭。這種方法利用了存儲(chǔ)在節(jié)點(diǎn)上的任何元數(shù)據(jù)（如最大元素、最小元素侮东、平均數(shù)等）圈盔，并利用它來(lái)生成鑰匙的大致位置。例如苗桂，如果我們?cè)谝粋€(gè)節(jié)點(diǎn)中尋找8药磺，我們知道10是最大的鍵，10（n+1）是最小的鍵（其中n是每個(gè)節(jié)點(diǎn)中的鍵的數(shù)量）煤伟，那么我們知道從最大的鍵向下2個(gè)槽開始搜索癌佩，因?yàn)樵谶@種情況下木缝，離最大的鍵一個(gè)槽的鍵必須是9。 ?盡管這是我們給出的最快的方法围辙，但由于其對(duì)具有某些屬性（如整數(shù)）和復(fù)雜性的鍵的適用性有限我碟，這種方法只在學(xué)術(shù)數(shù)據(jù)庫(kù)中出現(xiàn)。
四姚建、優(yōu)化
指針揮舞
因?yàn)锽+Tree的每個(gè)節(jié)點(diǎn)都存儲(chǔ)在緩沖池的一個(gè)頁(yè)面中矫俺，所以每次我們加載一個(gè)新的頁(yè)面時(shí)，都需要從緩沖池中獲取它掸冤，這需要鎖存和查找厘托。為了完全跳過(guò)這一步，我們可以用實(shí)際的原始指針來(lái)代替頁(yè)面ID（稱為 "swizzling"）稿湿，完全避免緩沖池的獲取铅匹。 ?與其手動(dòng)獲取整個(gè)樹并手動(dòng)放置指針，我們可以在正常遍歷索引時(shí)簡(jiǎn)單地存儲(chǔ)從頁(yè)面查詢中得到的指針饺藤。請(qǐng)注意包斑，我們必須跟蹤哪些指針被swizzled了，當(dāng)它們所指向的頁(yè)面被取消釘子涕俗，并成為受害者時(shí)罗丰，要把它們解凍成頁(yè)面ID。
批量插入
當(dāng)B+Tree最初建立時(shí)再姑，必須以通常的方式插入每個(gè)鍵萌抵，這將導(dǎo)致持續(xù)的分割操作。由于我們已經(jīng)給葉子提供了兄弟姐妹的指針询刹，如果我們構(gòu)建一個(gè)葉子節(jié)點(diǎn)的排序鏈表谜嫉，然后使用每個(gè)葉子節(jié)點(diǎn)的第一個(gè)鍵從下往上輕松地建立索引，那么初始插入數(shù)據(jù)的效率會(huì)高很多凹联。請(qǐng)注意沐兰，根據(jù)我們的情況，我們可能希望將葉子打包得越緊越好蔽挠，住闯，以節(jié)省空間，或者在每個(gè)葉子中留出空間澳淑，以便在有必要進(jìn)行分割之前進(jìn)行更多的插入比原。
前綴壓縮
大多數(shù)情況下，當(dāng)我們?cè)谕还?jié)點(diǎn)中擁有鍵時(shí)杠巡，每個(gè)鍵的一些前綴會(huì)有部分重疊（因?yàn)轭愃频逆I最終會(huì)在排序的B+Tree中緊挨著）量窘。 ?與其多次將這個(gè)前綴作為每個(gè)鍵的一部分來(lái)存儲(chǔ)，我們可以簡(jiǎn)單地在節(jié)點(diǎn)的開頭存儲(chǔ)一次前綴氢拥，然后在每個(gè)槽中只包括每個(gè)鍵的獨(dú)特部分蚌铜。
重復(fù)數(shù)據(jù)刪除
在一個(gè)允許非唯一鍵的索引的情況下锨侯，我們最終可能會(huì)出現(xiàn)葉子結(jié)點(diǎn)反復(fù)包含相同的鍵而附加不同的值。這方面的一個(gè)優(yōu)化是只寫一次鍵冬殃，然后在它后面加上所有相關(guān)的值囚痴。
后綴截?cái)?/b>
在大多數(shù)情況下，內(nèi)部節(jié)點(diǎn)中的關(guān)鍵條目只是作為路標(biāo)审葬，而不是其實(shí)際的關(guān)鍵值（因?yàn)榧词挂粋€(gè)關(guān)鍵存在于索引中深滚，我們?nèi)匀灰阉鞯降撞恳源_保它沒有被刪除）。我們可以利用這一點(diǎn)涣觉，只存儲(chǔ)正確路由探針到正確節(jié)點(diǎn)所需的最小前綴痴荐。
09 索引并發(fā)控制
在前兩節(jié)中討論的數(shù)據(jù)結(jié)構(gòu)中，我們都只考慮單線程訪問(wèn)的情況旨枯。實(shí)踐中蹬昌，絕大多數(shù)情況下，我們需要在并發(fā)訪問(wèn)情況下保證我們的數(shù)據(jù)結(jié)構(gòu)還能夠正常工作攀隔。除了 VoltDB，它用一個(gè)線程處理所有請(qǐng)求栖榨，徹底排除了并發(fā)的需要昆汹。
一、索引并發(fā)控制
到目前為止婴栽，我們假設(shè)我們所討論的數(shù)據(jù)結(jié)構(gòu)是單線程的满粗。然而，大多數(shù)DBMS需要允許多個(gè)線程安全地訪問(wèn)數(shù)據(jù)結(jié)構(gòu)愚争，以利用額外的CPU內(nèi)核和隱藏磁盤I/O停頓映皆。
并發(fā)控制協(xié)議是DBMS用來(lái)確保對(duì)共享對(duì)象進(jìn)行并發(fā)操作的"正確"結(jié)果的方法。
通常我們會(huì)從兩個(gè)層面上來(lái)理解并發(fā)控制的正確性：
●邏輯上的正確性:線程能夠讀取它應(yīng)該期望讀取的值轰枝。例如捅彻，一個(gè)線程應(yīng)該讀回它之前寫過(guò)的值。
●物理正確性:對(duì)象的內(nèi)部表示是健全的鞍陨，例如步淹，在數(shù)據(jù)結(jié)構(gòu)中沒有指針會(huì)導(dǎo)致線程讀取無(wú)效的內(nèi)存位置。
二诚撵、鎖與鎖扣
在討論DBMS如何保護(hù)其內(nèi)部元素時(shí)缭裆，鎖和鎖扣之間有一個(gè)重要的區(qū)別。
鎖
鎖是一個(gè)更高層次的邏輯基元寿烟，它保護(hù)數(shù)據(jù)庫(kù)的內(nèi)容( 如圖元澈驼、表、數(shù)據(jù)庫(kù))不受其他事務(wù)的影響筛武。事務(wù)將在整個(gè)持續(xù)時(shí)間內(nèi)持有一個(gè)鎖缝其。數(shù)據(jù)庫(kù)系統(tǒng)可以向用戶展示在運(yùn)行查詢時(shí)被持有的鎖需要能夠回滾變化购桑。
鎖存器
鎖存器是用于DBMS內(nèi)部數(shù)據(jù)結(jié)構(gòu)(例如，數(shù)據(jù)結(jié)構(gòu)氏淑、內(nèi)存區(qū)域)的關(guān)鍵部分的低級(jí)保護(hù)基元勃蜘，不受其他線程影響。鎖存器只在正在進(jìn)行的操作的持續(xù)時(shí)間內(nèi)保持假残。鎖存器不需要能夠回滾變化有兩種模式的鎖存器缭贡。
●讀:允許多個(gè)線程同時(shí)讀取同一個(gè)項(xiàng)目。并發(fā)讀
●寫 :只允許一個(gè)線程訪問(wèn)該項(xiàng)目辉懒。如果其他線程在任何模式下都持有寫鎖存器阳惹，那么一個(gè)線程就不能獲得寫鎖存器。一個(gè)持有寫鎖存器的線程也會(huì)阻止其他線程眶俩，獲得一個(gè)讀鎖存器莹汤。
三、閂鎖的實(shí)施
用來(lái)實(shí)現(xiàn)鎖存器的基本原理是通過(guò)現(xiàn)代CPU提供的原子比較和交換(CAS) 指令颠印。有了這個(gè)指令一個(gè)線程可以檢查一個(gè)內(nèi)存位置的內(nèi)容纲岭，看它是否有某個(gè)值。如果它有线罕，那么CPU將用一個(gè)新的值來(lái)交換舊的值止潮。否則，該內(nèi)存位置將保持不被修改钞楼。在DBMS中實(shí)現(xiàn)鎖存器有幾種方法喇闸。每種方法在工程復(fù)雜性和運(yùn)行時(shí)性能方面都有不同的權(quán)衡。這些測(cè)試和設(shè)置步驟是以原子方式進(jìn)行的( 也就是說(shuō)询件，在測(cè)試和設(shè)置步驟之間沒有其他線程可以更新值燃乍。
阻止操作系統(tǒng)Mutex
鎖存器的一個(gè)可能實(shí)現(xiàn)是操作系統(tǒng)內(nèi)置的互斥基礎(chǔ)設(shè)施。Linux提供了Futex (快 速用戶空間互斥.)宛琅，它由(1) 用戶空間的自旋鎖存器和(2) 操作系統(tǒng)級(jí)互斥組成刻蟹。如果DBMS能夠獲得用戶空間的鎖存器，那么鎖存器就會(huì)被設(shè)置夯秃。在DBMS看來(lái)座咆，它是一一個(gè)單一的鎖存器，盡管它包含兩個(gè).內(nèi)部鎖存器仓洼。如果DBMS不能獲取用戶空間的鎖存器介陶，那么它就會(huì)進(jìn)入內(nèi)核并試圖獲取-一個(gè)更昂貴的mutex。如果DBMS未能獲得第二二個(gè)mutex色建，那么線程就會(huì)通知操作系統(tǒng)它在mutex.上被阻塞了然后它就會(huì)被取消計(jì)劃哺呜。
在DBMS中，操作系統(tǒng)的mutex通常是- -個(gè)壞主意箕戳，因?yàn)樗怯刹僮飨到y(tǒng)管理的某残，有很大的開銷国撵。
●例如: std: :mutex
●優(yōu)點(diǎn)。使用簡(jiǎn)單玻墅，不需要在DBMS中進(jìn)行額外編碼介牙。
●缺點(diǎn)。由于操作系統(tǒng)的調(diào)度澳厢，昂貴且不可擴(kuò)展(每次鎖/解鎖調(diào)用約25 ns) 环础。
測(cè)試和設(shè)置旋轉(zhuǎn)鎖存器(TAS)
自旋鎖存器是操作系統(tǒng)互斥器的一個(gè)更有效的替代品，因?yàn)樗怯蒁BMSs控制的剩拢。自旋鎖基本上是線程試圖更新的內(nèi)存位置(例如线得，將-一個(gè)布爾值設(shè)置為真)。 -一個(gè)線程執(zhí)行CAS來(lái)嘗試更新內(nèi)存位置徐伐。DBMS 可以控制如果它不能得到鎖存器會(huì)發(fā)生什么贯钩。它可以選擇再次嘗試(例如，使用一個(gè)while循環(huán))或允許操作系統(tǒng)取消調(diào)度办素。因此角雷，這種方法給了DBMS更多的控制權(quán)，而不是OS的mutex摸屠，在OS的mutex中谓罗， 失敗的鎖存器將控制權(quán)交給OS。
●例如: std::atomic<T>季二。
●優(yōu)點(diǎn)。鎖定/解鎖操作是有效的(單指令鎖定/解鎖) 揭措。
●劣勢(shì)胯舷。不具有可擴(kuò)展性，也不適合緩存绊含，因?yàn)樵诙嗑€程中桑嘶，CAS指令會(huì)在不同的線程中被多次執(zhí)行。這些浪費(fèi)的指令在高競(jìng)爭(zhēng)環(huán)境中會(huì)堆積起來(lái);在操作系統(tǒng)看來(lái)躬充，這些線程很忙逃顶，盡管它們并沒有做有用的工作。這導(dǎo)致了緩存一致性問(wèn)題充甚，因?yàn)榫€程正在輪詢其他CPU的緩存線以政。
讀寫器鎖扣
Mutexes和Spin
Latches不區(qū)分讀/寫(也就是說(shuō)，它們不支持不同的模式)伴找。 DBMS需要一種允許并發(fā)讀取的方式盈蛮，所以如果應(yīng)用程序有大量的讀取，它將有更好的性能，因?yàn)樽x取者可以共享資源而不是等待檐束。讀者-寫者鎖存器允許鎖存器以讀或?qū)懩Ｊ奖怀钟信钔Ｋ櫽卸嗌倬€程持有該鎖存器少欺，并在每種模式下等待獲取該鎖存器稠通。讀者-寫者鎖存器使用前兩種鎖存器實(shí)現(xiàn)中的一種作為基元肌括，并有額外的邏輯來(lái)處理讀者寫者隊(duì)列枫浙。
這是在每種模式下對(duì)鎖存器的隊(duì)列請(qǐng)求朦拖。不同的DBMS對(duì)于如何處理隊(duì)列可以有不同的策略我磁。.
●示例: std: :shared mutex
●優(yōu)點(diǎn)孽文。允許并發(fā)的讀者。
●缺點(diǎn)十性。DBMS必須管理讀/寫隊(duì)列以避免餓死叛溢。由于額外的元數(shù)據(jù)，存儲(chǔ)開銷比自旋鎖存器大劲适。
四楷掉、哈希表鎖存
由于線程訪問(wèn)數(shù)據(jù)結(jié)構(gòu)的方式有限，因此在靜態(tài)哈希表中支持并發(fā)訪問(wèn)很容易霞势。例如烹植，所有線程在從槽中移動(dòng)到下一個(gè)槽時(shí)，都是朝同一個(gè)方向移動(dòng)(即自上而下)愕贡。 線程每次也只訪問(wèn)一個(gè)頁(yè)面/槽草雕。因此，在這種情況下固以，死鎖是不可能的墩虹，因?yàn)闆]有兩個(gè)線程可以爭(zhēng)奪對(duì)方持有的鎖存器。當(dāng)我們需要調(diào)整表的大小時(shí)憨琳，我們可以直接在整個(gè)表上取一個(gè)全局鎖存器來(lái)執(zhí)行操作诫钓。
動(dòng)態(tài)散列方案中的鎖存(例如，可擴(kuò)展)是一個(gè)更復(fù)雜的方案篙螟，因?yàn)橛懈嗟墓蚕頎顟B(tài)需要更新但一般的方法是相同的菌湃。
有兩種方法來(lái)支持哈希表的鎖存，它們?cè)阪i存的粒度上有所不同遍略。
●頁(yè)面鎖存器惧所。每個(gè)頁(yè)面都有自己的讀寫鎖存器，保護(hù)其全部?jī)?nèi)容绪杏。線程在訪問(wèn)一個(gè)頁(yè)面之前會(huì)獲得一個(gè)讀或?qū)戞i下愈。這降低了并行性，因?yàn)橐?次可能只有一個(gè)線程可以訪問(wèn)一個(gè)頁(yè)面寞忿，但是對(duì)于一個(gè)線程來(lái)說(shuō)驰唬，訪問(wèn)一個(gè)頁(yè)面中的多個(gè)槽會(huì)很快速，因?yàn)樗恍枰@取一一個(gè)鎖存器。
●槽的鎖扣叫编。每個(gè)槽都有自己的鎖存器辖佣。這增加了并行性，因?yàn)閮蓚€(gè)線程可以訪問(wèn)同一頁(yè)面上的不同槽搓逾。但是它增加了訪問(wèn)表的存儲(chǔ)和計(jì)算開銷卷谈， 因?yàn)榫€程必須為他們?cè)L問(wèn)的每個(gè)槽獲得一個(gè)鎖存器，每個(gè)槽必須為鎖存器存儲(chǔ)數(shù)據(jù)霞篡。DBMS可以使用單模式鎖存器(即旋轉(zhuǎn)鎖存器)來(lái)減少元數(shù)據(jù)和計(jì)算開銷世蔗，但要付出一-些并行性的代價(jià)。
也可以直接使用比較和交換(CAS)指令創(chuàng)建-一個(gè)無(wú)閂鎖的線性探測(cè)哈希表朗兵。在- -一個(gè)槽的插人可以通過(guò)嘗試將- 個(gè)特殊的"空. "值與我們想要插入的元組進(jìn)行比較和交換來(lái)實(shí)現(xiàn)污淋。如果失敗了， 我們可以探測(cè)下一個(gè)槽余掖，繼續(xù)下去.直到成功寸爆。
五、B+樹形鎖存
B+Tree鎖存的挑戰(zhàn)在于防止以下兩個(gè)問(wèn)題盐欺。
●試圖同時(shí)修改-一個(gè)節(jié)點(diǎn)的內(nèi)容的線程赁豆。
●一個(gè)線程遍歷樹，而另一個(gè)線程拆分/合并結(jié)點(diǎn)冗美。
閂鎖抓取/耦合是一種協(xié)議魔种，允許多個(gè)線程同時(shí)訪問(wèn)/修改B+Tree。其基本思想如下粉洼。
1.為父方獲取閂鎖节预。
2.為孩子準(zhǔn)備好鎖扣。
3.如果子節(jié)點(diǎn)被認(rèn)為是"安全的"属韧，則釋放父節(jié)點(diǎn)的閂鎖心铃。一個(gè)."安全"的節(jié)點(diǎn)是在更新時(shí)不會(huì)分裂、合并或重新分配的節(jié)點(diǎn)挫剑。.注意，"安全"的概念取決 于操作是插入還是刪除柱衔。-一個(gè)完整的節(jié)點(diǎn)對(duì)于刪除來(lái)說(shuō)是"安全"的樊破，因?yàn)椴恍枰喜ⅲ?但是對(duì)于插入來(lái)說(shuō)就不"安全"了，因?yàn)槲覀兛赡苄枰指罟?jié)點(diǎn)唆铐。請(qǐng)注意哲戚，讀鎖存器不需要擔(dān)心"安全"條件。
閂式捕蟹的基本協(xié)議艾岂。
●搜索顺少。從根部開始，往下走，反復(fù)取得子代的鎖扣脆炎，然后解開父代的鎖扣梅猿。
●插入/刪除。從根部開始秒裕，往下走袱蚓，根據(jù)需要獲得X個(gè)鎖扣。一旦孩子被鎖住几蜻，檢查它是否安全喇潘。如果孩子是安全的，釋放其所有祖先的鎖扣梭稚。
從正確性的角度來(lái)看颖低，釋放鎖存器的順序并不重要。然而弧烤，從性能的角度來(lái)看忱屑， 最好是釋放樹中較高位置的鎖存器，因?yàn)樗鼈冏钄嗔藢?duì)較大部分葉子節(jié)點(diǎn)的訪問(wèn)扼褪。改進(jìn)的閂鎖抓取協(xié)議想幻。基本鎖存器抓取算法的問(wèn)題是话浇，每次插人/刪除操作時(shí)脏毯，交易總是在根.上獲得一個(gè)獨(dú)占鎖存器。這限制了并行性幔崖。相反食店，我們可以假設(shè)調(diào)整大小(即分割/合并節(jié)點(diǎn))的情況很少，因此事務(wù)可以獲得共享鎖存器赏寇，直到葉節(jié)點(diǎn)吉嫩。每個(gè)事務(wù)都會(huì)假設(shè)通往目標(biāo)葉子節(jié)點(diǎn)的路徑是安全的，并使用READ鎖存器和抓取來(lái)到達(dá)它并進(jìn)行驗(yàn)證嗅定。如果葉子節(jié)點(diǎn)不安全自娩，那么我們就放棄，并執(zhí)行之前的算法渠退，即我們獲取WRITE鎖存器忙迁。
●搜索。與以前的算法相同碎乃。
●插入/刪除姊扔。像搜索一樣設(shè)置READ鎖存器，進(jìn)入葉子梅誓，在葉子上設(shè)置WRITE鎖存器恰梢。如果葉子不安全佛南，釋放所有以前的鎖存器，并使用以前的插入/刪除協(xié)議重新開始交易嵌言。
葉子節(jié)點(diǎn)掃描
這些協(xié)議中的線程以"自上而下"的方式獲取鎖存器嗅回。這意味著一個(gè)線程只能從其當(dāng)前節(jié)點(diǎn)以下的節(jié)點(diǎn)獲取鎖存器。如果想要的鎖存器不可用呀页，線程必須等待妈拌，直到它變得可用。鑒于此蓬蝶，不可能出現(xiàn)死鎖尘分。
然而，葉子節(jié)點(diǎn)掃描很容易出現(xiàn)死鎖丸氛，因?yàn)楝F(xiàn)在我們有線程試圖同時(shí)在兩個(gè)不同的方向上獲得外鎖(例如培愁，線程1試圖刪除，線程2進(jìn)行葉子節(jié)點(diǎn)掃描)缓窜。 索弓|鎖不支持死鎖檢測(cè)或避免定续。
因此，程序員處理這個(gè)問(wèn)題的唯一方法是 通過(guò)編碼紀(jì)律禾锤。葉子節(jié)點(diǎn)兄弟姐妹的鎖存器獲取協(xié)議必須支持"無(wú)等待"模式私股。也就是說(shuō)，B+tree代碼必須應(yīng)對(duì)鎖存器獲取失敗的問(wèn)題恩掷。由于鎖存器旨在被(相對(duì))短暫地持有倡鲸，如果一個(gè)線程試圖在葉子節(jié)點(diǎn)上獲取鎖存器，但該鎖存器不可用黄娘，那么它應(yīng)該迅速中止其操作(釋放它所持有的任何鎖存器)并重新啟動(dòng)操作峭状。
酷酷酷酷酷
