主存存取原理

主存的構成

主存儲器（簡稱主存或內(nèi)存）包括存取體、各種邏輯部件及控制電路等。存儲體由許多存儲單元組成，每個存儲單元又包含若干個存儲元件，每個存儲元件能寄存一位二進制代碼“0”或“1”。這樣，一個存儲單元可以存儲一串二進制代碼，這串二進制代碼稱為存儲字，這串二進制代碼的位數(shù)稱為存儲字長，可以是8位、16位或者32位等。

主存與CPU的聯(lián)系

MAR（Memory Address Register）是存儲器地址寄存器，用來存放欲訪問的存儲單元的地址，其位數(shù)對應存儲單元的個數(shù)（若MAR為10位，則有210=1024個存儲單元，記為1k）。

MDR（Memory Data Register）是存儲器數(shù)據(jù)寄存器，用于存放從存儲體某單元取出的代碼或準備往某存儲單元存入的代碼，其位數(shù)與存儲字長相等。

現(xiàn)代計算機一般將MAR和MDR集成在CPU芯片中。

主存的存取過程

如果把存儲體看做是一棟大樓，那么每個存儲單元可以看成這棟大樓里的每個房間，每個存儲元可以看做房間里的一張床位，床位有人相當于“1”，無人相當于“0”。每個房間都需要一個房間號，便于我們找到房間的位置。同樣，可以賦予每個存儲單元一個編號，稱為存儲單元的地址號。

主存的工作方式就是按照存儲單元的地址號來實現(xiàn)對存儲字各位的存（寫入）、?。ㄗx出）。

現(xiàn)代主存的結構和存取原理比較復雜，這里拋卻具體差別，抽象出一個十分簡單的存取模型來說明主存的工作原理。

主存的存取過程如下：

當系統(tǒng)需要讀取主存時，首先由CPU將該字的地址送到MAR,經(jīng)地址總線送至主存，然后發(fā)出讀命令。主存接到讀命令后，根據(jù)地址定位到指定存儲單元，然后將此存儲單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取。

寫主存的過程類似，若要向主存存入一個信息字時，首先CPU將該字要存入的主存單元的地址經(jīng)MAR送到地址總線，并將信息字送入MDR，然后向主存發(fā)出寫命令，主存接到寫命令后，便將數(shù)據(jù)總線上的信息寫入到對應地址總線指出的主存單元中。

畫外音：實際上主存存取的過程并沒有這么簡單，還需要經(jīng)過經(jīng)過地址譯碼（邏輯地址—>物理地址）等過程。

磁盤存取原理

我們知道，索引本身也很大，不可能全部存儲在內(nèi)存中（根節(jié)點常駐內(nèi)存），一般以文件形式存儲在磁盤上。那么問題來了，索引檢索需要磁盤I/O操作。與內(nèi)存不同，磁盤I/O存在機械運動耗費，相對于內(nèi)存存取，I/O存取的消耗要高幾個數(shù)量級。

磁盤的構成

磁盤的整體結構示意圖：

一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉(zhuǎn)動（各個磁盤必須同步轉(zhuǎn)動）。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內(nèi)容。磁頭不能轉(zhuǎn)動，但是可以沿磁盤半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的。

磁盤盤片示意圖：

盤片被劃分成一系列同心環(huán)，圓心是盤片中心，每個同心環(huán)叫做一個磁道，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段，每個段叫做一個扇區(qū)，每個扇區(qū)是磁盤的最小存儲單元。

磁盤的存取過程：

當需要從磁盤讀取數(shù)據(jù)時，系統(tǒng)會將數(shù)據(jù)邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數(shù)據(jù)在哪個磁道，哪個扇區(qū)。

為了讀取這個扇區(qū)的數(shù)據(jù)，需要將磁頭放到這個扇區(qū)上方，為了實現(xiàn)這一點：

1. 首先必須找到柱面，即磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間
2. 然后目標扇區(qū)旋轉(zhuǎn)到磁頭下，即磁盤旋轉(zhuǎn)將目標扇區(qū)旋轉(zhuǎn)到磁頭下。這個過程耗費的時間叫做旋轉(zhuǎn)時間

所以一次訪盤請求（讀/寫）完成過程由三個動作組成：

1. 尋道（時間）：磁頭移動定位到指定磁道
2. 旋轉(zhuǎn)延遲（時間）：等待指定扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過
3. 數(shù)據(jù)傳輸（時間）：數(shù)據(jù)在磁盤與內(nèi)存之間的實際傳輸

局部性原理與磁盤預讀

由于存儲介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百萬分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節(jié)，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計算機科學中著名的局部性原理：

由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉(zhuǎn)時間），因此對于具有局部性的程序來說，預讀可以提高I/O效率。

預讀的長度一般為頁（page）的整倍數(shù)。頁是計算機管理存儲器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊，每個存儲塊稱為一頁（在許多操作系統(tǒng)中，頁的大小通常為4k），主存和磁盤以頁為單位交換數(shù)據(jù)。當程序要讀取的數(shù)據(jù)不在主存中時，會觸發(fā)一個缺頁異常，此時系統(tǒng)會向磁盤發(fā)出讀盤信號，磁盤會找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中，然后異常返回，程序繼續(xù)運行。

數(shù)據(jù)庫為什么選用B-/+Tree索引

之前提到過，SQL優(yōu)化的一個重要原則是減少磁盤I/O次數(shù)，磁盤I/O次數(shù)也是評價索引結構的優(yōu)劣的指標之一。

B-Tree分析：

根據(jù)B-Tree的定義，可知檢索一次最多需要訪問h（B-Tree的高度）個節(jié)點。數(shù)據(jù)庫系統(tǒng)的設計者巧妙利用了磁盤預讀原理，將一個節(jié)點的大小設為等于一個頁，這樣每個節(jié)點只需要一次I/O就可以完全載入。但是邏輯上存儲在一個頁里并不代表物理上也存儲在一個頁里，為了達到這個目的，每次新建節(jié)點時，直接申請一個頁的空間，這樣就保證一個節(jié)點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現(xiàn)了一個節(jié)點只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O，因為根節(jié)點會常駐內(nèi)存。復雜度為O(logdN)。一般實際應用中，出度d是非常大的數(shù)字，通常超過100，因此h非常?。ㄍǔ２怀^3）。所以B-Tree作為索引結構效率是非常高的。這也是為什么數(shù)據(jù)庫不選用紅黑樹作為索引（數(shù)據(jù)結構）的原因，一是因為紅黑樹的高度h要大的多；二是紅黑樹節(jié)點在物理上可能是單獨存儲的，無法利用局部性原理。復雜度為O(h)，效率明顯比B-Tree差的多。

B+Tree分析：