數(shù)據(jù)庫物理層簡(jiǎn)介
在之前的課程中命雀，我們主要介紹了數(shù)據(jù)庫系統(tǒng)中“較高層次”的結(jié)構(gòu)，例如關(guān)系模型斩箫、表的結(jié)構(gòu)等邏輯或概念模型吏砂，這是數(shù)據(jù)庫符合數(shù)據(jù)庫最初創(chuàng)建的原因的撵儿。因?yàn)槲覀兿胱寯?shù)據(jù)庫的用戶盡可能地只關(guān)注于如何滿足和實(shí)現(xiàn)自己的需求，而不用考慮數(shù)據(jù)是如何在數(shù)據(jù)庫中存儲(chǔ)的或者如何被查詢到的狐血，這樣“封裝”的思想在程序員世界中經(jīng)车硇可以見到。
但是了解一下數(shù)據(jù)庫在物理層面是如何組織的匈织，可以幫助我們對(duì)數(shù)據(jù)庫管理系統(tǒng)有更深的了解浪默。首先在這一節(jié)中，我們將向大家介紹一些常見的存儲(chǔ)介質(zhì)缀匕。
常見的物理存儲(chǔ)介質(zhì)
在計(jì)算機(jī)系統(tǒng)中纳决，有很多種物理存儲(chǔ)介質(zhì)，它們的存取速度和價(jià)格各有不同乡小，因此它們各自適用的場(chǎng)景也不同岳链，常見的物理存儲(chǔ)介質(zhì)有以下幾種：
緩存（cache）
緩存是讀寫速度最快且單位花費(fèi)最高的存儲(chǔ)介質(zhì)。一般來說劲件，緩存的管理都是由操作系統(tǒng)進(jìn)行的，在數(shù)據(jù)庫中我們一般不涉及這類存儲(chǔ)介質(zhì)约急；主存（main memory）
主存中存儲(chǔ)的是操作指令和相關(guān)操作數(shù)據(jù)零远，它會(huì)與緩存有直接的數(shù)據(jù)交換。一般來說主存儲(chǔ)器的大小都不足以容納整個(gè)數(shù)據(jù)庫厌蔽，并且斷電后主存中的數(shù)據(jù)將會(huì)丟失牵辣；閃存（flash memory）
閃存也是計(jì)算機(jī)內(nèi)存儲(chǔ)器的一部分，與主存相比奴饮，它斷電后數(shù)據(jù)不丟失纬向。它讀出數(shù)據(jù)的速度與主存相當(dāng)，但寫入數(shù)據(jù)較為緩慢戴卜，這是由于它在寫入數(shù)據(jù)時(shí)需要事先擦除某個(gè)數(shù)據(jù)區(qū)塊的內(nèi)容逾条，但是如果能妥善地管理數(shù)據(jù)塊，它的寫入速度還是非惩栋可觀的师脂。我們通常用到的 USB 就是閃存的一種。磁盤存儲(chǔ)（magnetic disk storage）
磁盤存儲(chǔ)器是最常用的存儲(chǔ)數(shù)據(jù)庫數(shù)據(jù)的介質(zhì)江锨，通常情況下吃警，數(shù)據(jù)庫的全體數(shù)據(jù)都存儲(chǔ)在磁盤存儲(chǔ)器中，在使用數(shù)據(jù)庫時(shí)啄育，系統(tǒng)從磁盤存儲(chǔ)器中將相應(yīng)的數(shù)據(jù)放入主存中進(jìn)行操作酌心，最終從主存寫回磁盤存儲(chǔ)器。磁盤存儲(chǔ)器的價(jià)格較低挑豌，存儲(chǔ)速度中等安券，很適合存儲(chǔ)較大量的數(shù)據(jù)墩崩。光存儲(chǔ)（optical storage）
最常見的光存儲(chǔ)器包括 CD、DVD 等完疫，它們只能被寫入一次泰鸡，寫入之后只能讀取，因此也被稱為 WORM-disk（write-once read-many disk）壳鹤。磁帶存儲(chǔ)（tape storage）
在進(jìn)行數(shù)據(jù)庫備份或存儲(chǔ)檔案數(shù)據(jù)時(shí)盛龄，經(jīng)常用到磁帶存儲(chǔ)器。它的價(jià)格十分低廉但存儲(chǔ)容量很大芳誓，不容易損壞并且可以長(zhǎng)時(shí)間保存余舶。因此在存儲(chǔ)衛(wèi)星產(chǎn)生的數(shù)據(jù)、備份規(guī)模較大或保存時(shí)間較長(zhǎng)的數(shù)據(jù)時(shí)锹淌，會(huì)用到磁帶存儲(chǔ)匿值。
這幾種存儲(chǔ)器從上至下，讀寫速度越來越慢赂摆、存儲(chǔ)容量越來越大挟憔、價(jià)格越來越便宜。目前看來烟号，還沒有既物美又價(jià)廉的存儲(chǔ)介質(zhì)绊谭，每種介質(zhì)都有適合它發(fā)揮能量的場(chǎng)景。
練習(xí)
數(shù)據(jù)是如何被存儲(chǔ)的
定長(zhǎng)記錄的兩個(gè)問題
不定長(zhǎng)記錄
文件組織方式
索引存在的意義
稠密索引
很明顯汪拥，在檢索記錄的時(shí)候达传，使用稠密索引可以更快的定位到目標(biāo)記錄，但是稀疏索引可以節(jié)省占用的空間迫筑，并且減少由于維護(hù)和操作指針帶來的開銷宪赶。在實(shí)際的數(shù)據(jù)庫中，我們必須綜合考慮效率脯燃、占用空間和開銷搂妻，爭(zhēng)取達(dá)到某個(gè)平衡。通常采用的做法是辕棚，根據(jù)每次能被內(nèi)存讀入的數(shù)據(jù)塊大小設(shè)置稀疏索引叽讳，每一個(gè)數(shù)據(jù)塊對(duì)應(yīng)一個(gè)索引項(xiàng)，這樣可以很好地節(jié)省空間坟募。等到占用空間并不大的數(shù)據(jù)塊讀入到讀寫速度較快的內(nèi)存之中岛蚤，就可以采取遍歷記錄的方式進(jìn)行查找，這樣做的效率是很可觀的懈糯。
但是這樣做就足夠了嗎涤妒？這可不一定。
多級(jí)索引
多級(jí)索引在數(shù)據(jù)庫系統(tǒng)中應(yīng)用十分廣泛赚哗，它是一種非常理想的索引方式她紫，在下一節(jié)中我們將為大家介紹實(shí)際數(shù)據(jù)庫中常常采用的一種多級(jí)索引結(jié)構(gòu) B+ 樹索引硅堆。不過我們先做一道題鞏固一下今天所學(xué)的知識(shí)。
練習(xí)
什么是 B+ 樹
順序索引的一個(gè)致命缺點(diǎn)就是隨著數(shù)據(jù)量的增加贿讹，在索引中搜索的效率不斷下降渐逃。雖然效率的下降速度可以通過重新組織文件的方式有所延緩，但是高頻率地進(jìn)行文件組織更新也是我們不愿意看到的民褂，它會(huì)耗費(fèi)大量的時(shí)間和內(nèi)存茄菊。
B+ 樹索引是一種可以保證索引效率的結(jié)構(gòu)，不管數(shù)據(jù)庫中添加或刪除多少數(shù)據(jù)赊堪，查詢的效率是穩(wěn)定的面殖。這是因?yàn)樗且环N 平衡樹（balanced tree），從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每一條路徑的長(zhǎng)度是一樣的哭廉。它的每個(gè)非葉子節(jié)點(diǎn)都有 n/2 到 n 的子節(jié)點(diǎn)脊僚，其中n在每一棵平衡樹中為一個(gè)確定的值。
從本質(zhì)上講遵绰，B+ 樹仍然是一種多級(jí)索引辽幌，但是它的結(jié)構(gòu)不同于順序的多級(jí)索引。下圖是一個(gè) n = 5 的 B+ 樹索引結(jié)構(gòu)椿访。
在 B+ 樹中乌企，非葉子結(jié)點(diǎn)上存儲(chǔ)著子樹中最大或最小的關(guān)鍵字，這樣一來所有的葉子節(jié)點(diǎn)都是按照從小到大或從大到小的順序排列的赎离。如果將每一個(gè)非葉子節(jié)點(diǎn)的子樹順序交換，相應(yīng)的端辱，葉子節(jié)點(diǎn)的排列順序也要顛倒梁剔。
練習(xí)
為啥用哈希
哈希函數(shù)
哈希桶的溢出
哈希索引
