第一篇基礎篇
第1章概述31.1數據庫繫統概述3
1.1.1數據庫繫統的基本概念3
1.1.2為什麼使用數據庫繫統5
1.2數據庫技術的發展5
1.2.1數據模型推動數據庫技術發展6
1.2.2應用需求推動數據庫技術發展9
1.2.3計算平臺推動數據庫技術發展13
1.3數據庫管理繫統組成17
1.3.1數據庫管理繫統的功能結構17
1.3.2數據庫管理繫統的模式結構19
1.3.3數據庫管理繫統的體繫結構20
1.3.4數據庫管理繫統的執行過程21
1.4我國數據庫的發展歷程23
1.5本章小結25
習題25
第2章關繫數據模型27
2.1關繫模型的數據結構及形式化定義27
2.1.1關繫概述27
2.1.2關繫模式30
2.1.3關繫數據庫30
2.1.4關繫模型的存儲結構31
2.2關繫代數31
2.2.1傳統的集合運算31
2.2.2專門的關繫運算32
2.3關繫的完整性34
2.3.1實體完整性34
2.3.2參照完整性35
2.3.3用戶定義的完整性36
2.4本章小結36習題36
第3章關繫數據庫標準語言SQL37
3.1SQL概述37
3.2數據定義37
3.2.1模式的定義與刪除37
3.2.2基本表的定義、修改與刪除38
3.2.3索引的創建41
3.3基本SQL查詢41
3.3.1單表查詢41
3.3.2連接查詢43
3.3.3集合查詢45
3.3.4空值查詢46
3.3.5聚集查詢46
3.4數據更新47
3.4.1插入數據47
3.4.2修改數據48
3.4.3刪除數據48
3.5視圖49
3.5.1定義視圖49
3.5.2查詢視圖50
3.5.3更新視圖50
3.6本章小結50
習題51
實驗51
第4章高級SQL53
4.1復雜SQL查詢53
4.1.1嵌套查詢53
4.1.2遞歸查詢55
4.1.3基於派生表的查詢56
4.2數據庫完整性57
4.2.1實體完整性57
4.2.2參照完整性57
4.2.3用戶定義的完整性58
4.3數據庫安全性58
4.3.1數據庫安全性等級58
4.3.2自主存取控制60
4.3.3強制存取控制61
4.4數據庫編程62
4.4.1過程化SQL62
4.4.2存儲過程與函數65
4.4.3觸發器65
4.5本章小結66
習題67
實驗67
第二篇數據存取篇
第5章存儲管理715.1物理存儲繫統71
5.1.1存儲介質概述71
5.1.2常用存儲介質72
5.1.3磁盤I/O性能的提升策略75
5.2數據組織76
5.2.1數據庫的邏輯與物理組織方式76
5.2.2記錄表示77
5.2.3塊的組織78
5.2.4關繫表的組織81
數據存儲84
5.4緩衝區85
5.4.1緩衝區管理85
5.4.2頁面置換策略86
5.5本章小結88
習題89
實驗89
第6章索引91
6.1順序表的索引92
6.1.1稠密索引92
6.1.2稀疏索引93
6.1.3多級索引94
6.2輔助索引95
6.3B 樹索引96
6.3.1B 樹索引的結構96
6.3.2B 樹索引的查詢97
6.3.3B 樹索引的維護98
6.4哈希索引100
6.4.1靜態哈希索引100
6.4.2動態哈希索引102
6.5Bitmap索引106
6.5.1Bitmap索引概述106
6.5.2編碼Bitmap索引107
6.6本章小結109
習題109
實驗110
第三篇查詢處理篇
第7章查詢處理1137.1查詢處理概述113
7.2查詢編譯114
7.2.1查詢編譯概述114
7.2.2詞法與語法分析115
7.2.3語義分析118
7.2.4查詢優化119
7.3物理操作符121
7.3.1物理操作符的代價模型121
7.3.2掃描操作122
7.3.3排序操作124
7.3.4連接操作126
7.3.5去除重復值132
7.3.6分組聚集132
7.3.7集合操作133
7.4本章小結133
習題134
實驗134
第8章查詢優化135
8.1查詢優化概述135
8.1.1查詢優化的意義135
8.1.2查詢優化的方法136
8.1.3查詢優化器的結構137
8.2關繫代數表達式等價變換規則138
8.2.1選擇運算的相關規則138
8.2.2投影運算的相關規則139
8.2.3連接運算的相關規則140
8.2.4去重運算的相關規則143
8.2.5聚集運算的相關規則144
8.2.6集合運算的相關規則147
8.3統計信息147
8.4基數估算148
8.4.1選擇運算結果集的估算149
8.4.2連接運算結果集的估算152
8.4.3其他運算結果集的估算153
8.5多表連接的優化154
8.5.1多表連接的查詢計劃樹154
8.5.2多表連接順序的搜索空間155
8.5.3動態規劃157
8.5.4貪心算法160
8.6本章小結161
習題161
實驗162
第9章查詢執行163
9.1查詢執行概述163
9.1.1物化164
9.1.2流水線165
9.1.3查詢計劃的執行166
9.2查詢執行模型167
9.2.1火山模型167
9.2.2向量執行模型168
9.3查詢並行執行169
9.3.1並行執行概述169
9.3.2並行執行模型170
9.3.3並行執行算法172
9.4查詢編譯執行173
9.5本章小結174
習題175
實驗175
第四篇事務處理篇
第10章事務處理概述17910.1事務基本概念179
10.1.1事務的定義179
10.1.2事務的ACID特性181
10.2數據異常與隔離級別182
10.2.1事務的執行模型182
10.2.2數據異常183
10.2.3隔離級別186
10.3正確的調度187
10.3.1調度與串行調度187
10.3.2可串行化調度189
10.3.3衝突可串行化調度190
10.3.4基於優先圖的衝突可串行化驗證191
10.4本章小結192
習題192
實驗193
第11章並發控制195
11.1兩階段封鎖協議196
11.1.1基本實現技術196
11.1.2嚴格與強嚴格兩階段封鎖協議198
11.1.3死鎖預防實現技術200
11.1.4小結202
11.2時間戳排序協議203
11.2.1基本實現技術203
11.2.2避免級聯回滾205
11.2.3小結207
11.3樂觀並發控制協議208
11.3.1基本實現技術208
11.3.2小結210
11.4三級封鎖協議210
11.5多版本並發控制技術212
11.5.1基本實現技術212
11.5.2快照隔離214
11.5.3寫偏序214
11.5.4版本管理215
11.6本章小結217
習題217
實驗218
第12章故障恢復219
12.1故障恢復概述219
12.1.1故障的分類219
12.1.2事務讀寫的訪問模式220
12.1.3故障下數據一致性的破壞222
12.2恢復的基本實現技術225
12.2.1日志文件225
12.2.2WAL日志226
12.2.3備份227
12.3恢復的基本原理229
12.3.1事務故障的恢復229
12.3.2繫統故障的恢復230
12.3.3介質故障的恢復232
12.4ARIES算法233
12.4.1繫統正常運行時的日志記錄233
12.4.2WAL算法的實現234
12.4.3模糊檢查點235
12.4.4繫統故障恢復236
12.5本章小結238
習題238
實驗240
參考文獻241

數據庫是信息技術領域的核心技術之一，是最重要的基礎軟件之一，在信息技術的發展中具有舉足輕重的地位。本書重點討論數據庫管理繫統的基礎知識、基本原理和關鍵實現技術。
1. 編寫緣由
2022年年初，我們針對國內本科生數據庫教學、國外頂尖高校本科生數據庫教學、企業對數據庫人纔滿意度等進行了一繫列調研，調查對像包括國內98所高校的170個數據庫課堂，CS Ranking數據庫排名前50的26所海外高校的37個課堂，以及部分用人企業。調查結果顯示，國內數據庫教學內容主要集中在數據庫及數據庫管理繫統基本概念、SQL、數據庫設計等內容上。海外70%以上的被調查高校提供了數據庫管理繫統內核實現的課程。國內用人企業對高校輸送的數據庫人纔也不滿意，認為難以找到了解數據庫內核實現的人纔，需要進行較長時間的再培訓。究其原因，近年來隨著中美關繫的變化，國內企業越來越重視研發具有自主知識產權的繫統軟件，而國內高校的課堂教學內容未能及時進行調整。
中國人民大學信息學院從20世紀90年代開始，在研究生中開設數據庫管理繫統原理與實現的課程，但這個課不是針對零基礎的學生，其先修課是數據庫繫統概論。從2020年開始，我們對圖靈實驗班（計算機撥尖班）進行數據庫教學改革，針對零基礎的學生講授數據庫內核實現技術，並研發了相應的實驗平臺RucBase。四年的實踐證明，這種改革是可行的、成功的。但在教學中我們也發現，國內數據庫概論類教材百花齊放，而數據庫管理繫統實現類教材鳳毛麟角。
2022年，中國人民大學牽頭了“101計劃”數據庫繫統課程建設以及“101計劃”數據庫繫統課程虛擬教研室，參與單位包括清華大學、北京大學、浙江大學、西北工業大學、哈爾濱工業大學、山東大學、武漢大學、西安電子科技大學、中國科技大學、華東師範大學、中山大學、東南大學、北京交通大學。在此平臺上，大家合力完成了海外高校數據庫教學調研，繪制了知識圖譜，撰寫了知識點教案。同時 “101計劃”也給我們提供了契機，讓我們終於下決心結合多年的授課經驗，撰寫了本書。
2. 內容與特色
本書面向數據庫零基礎的學生，繫統講授數據庫的基本概念、SQL、數據庫管理繫統基本原理與實現技術。全書分為4篇共12章。
第一篇為基礎篇，包括概述、關繫數據模型、關繫數據庫標準語言SQL、高級SQL，共4章。
第二篇為數據存取篇，包括存儲管理、索引，共2章。
第三篇為查詢處理篇，包括查詢處理、查詢優化、查詢執行，共3章。
第四篇為事務處理篇，包括事務處理概述、並發控制、故障恢復，共3章。
本書具有如下特色:
(1) 視角新穎。有別於傳統數據庫教材教學生如何“用數據庫”，本書重點教學生如何“造數據庫”，從基本概念與基本原理，到數據庫核心組件的實現技術，由淺入深，脈絡清晰。
(2) 內容全面繫統。面向數據庫零基礎的學生，在知識點選取上秉承“更基礎、更核心”的理念，首先從數據庫基本概念入手，講解數據模型、數據庫的模式結構、關繫模型、SQL、SQL編程等內容，然後在此基礎上，繫統地介紹關繫數據庫的存儲管理、查詢處理、事務管理等知識點。
(3) 實現原理與實現算法合理取舍。本書以開源數據庫繫統為基礎，繫統講解數據庫內核實現原理的同時，配合部分實現算法，在易於理解與深度之間取得平衡。
(4) 提供配套實驗平臺。面向零基礎學生講授數據庫管理繫統內核實現的最大難點是如何做實驗，為此我們研制了實驗平臺並在GitHub上開源。該實驗平臺為學生搭建好數據庫管理繫統的整體框架，配合本書的知識點設計了若干任務，每項任務又細化為多項子任務，供學生以“完形填空”的方式進行實踐，包括按照要求設計數據結構、設計算法等。實驗平臺可以自動完成對學生實驗的評估。
對於本書的使用建議如下:
(1) 對於數據庫零基礎的學生，可以完整地使用本書進行教學。
(2) 對於已經掌握數據庫基礎知識，想進一步了解數據庫管理繫統實現原理與技術的學生，可以學習本書的第二、三、四篇。
3. 編寫過程與分工
本書編寫過程歷時一年零八個月，其中經歷了大綱編寫和審定、書稿撰寫和修改、龍岩導教班試用和反饋，再次修改交審稿組審稿，根據審稿意見修改和定稿。主要編寫過程如下:
2022年3月，完成編寫大綱，提交“101計劃”秘書處。
2022年12月1日，“101計劃”秘書處組織了對大綱以及樣章的評審，評審組長為西北工業大學李戰懷教授，評審專家包括中國人民大學王珊教授、清華大學周立柱教授、哈爾濱工業大學高宏教授、東北大學楊曉春教授、山東大學彭朝暉教授。會後，我們按照專家組的意見對大綱進行了修訂，並於2023年6月30日完成了教材初稿。
2023年7月18日至22日，我們在龍岩召開了“數據庫管理繫統原理與實現”導教班，來自全國24所高校的34位教師參加了此次導教班。在導教班上我們印發了初稿，請老師們分組審閱並提出修改意見。
2023年8月至9月，我們按照導教班提出的修改意見，對書稿進行了修改和完善。
2023年10月，編寫組內部交換互審，並進行再次修改。
2023年10月底，將書稿提交給評審委員會審稿。評審委員會由西北工業大學李戰懷教授任組長，評審委員包括武漢大學彭志勇教授、華東師範大學王曉玲教授、寧夏大學杜方教授。評審專家認真審閱了書稿，並召開評審會進行討論和意見反饋。會後，我們按照專家組的意見再次進行了認真修改，最終定稿，並提交出版社。
4. 致謝
本書的完成凝集了很多人的心血。焦敏老師幫助完成了本書的排版工作，博士生劉宇涵幫助完成了本書的圖片修改工作。
由西北工業大學李戰懷教授、武漢大學彭志勇教授、華東師範大學王曉玲教授、寧夏大學杜方教授組成的教材評審委員會，由西北工業大學李戰懷教授、中國人民大學王珊教授、清華大學周立柱教授、哈爾濱工業大學高宏教授、東北大學楊曉春教授、山東大學彭朝暉教授組成的教材大綱和樣章評審委員會對本書的編寫提出了寶貴的修改意見。
在龍岩導教班上，山東大學彭朝暉，華東師範大學王曉玲，寧夏大學杜方，哈爾濱工業大學鄒兆年，西北工業大學李寧、趙曉南，東北大學聶鐵錚、劉思宇，內蒙古大學王少鵬，揚州大學陳纔扣，廈門理工學院王琰，天津工業大學榮垂田，北京信息科技大學車蕾、王曉波，華中科技大學瞿彬彬、楊茂林，北京郵電大學郭迎，西安電子科技大學夏小芳，西安電子科技大學李翠敏、王小兵，大連海事大學張俊、張德珍，北京化工大學尚穎，吉林大學王新穎、康輝，昆明理工大學遊進國、賈連印，華中師範大學羅昌銀，山西農業大學樊建軍、李小凡，西南科技大學張世鈴，成都理工大學李紅軍，廣東理工學院陳偉蓮、梁玉英等審閱了本書初稿，並提出了中肯的建議。
在書稿的撰寫和評審過程中，清華大學出版社龍啟銘編輯提供了諸多幫助。
在此，一並向上述人員表示衷心的感謝。
本書編寫分工情況如下: 第一篇由杜小勇、陳晉川完成；第二篇由陳紅、馮玉完成；第三篇由馮玉、張孝完成；第四篇由盧衛完成。杜小勇和陳紅審定了全書。
在編寫過程中，編者參考了國外相關教材、專著、論文和網上資料，努力跟蹤數據庫管理繫統的新發展和新技術，並有選擇地將其納入本書。由於作者水平有限，書中難免有不足之處 ，敬請讀者不吝賜教。

杜小勇2023年10月於北京目錄