亚洲精品免费视频,av亚洲在线,天天干女人网

數據結構以及算法

索引的本質其實就是一種數據結構。我們都希望查詢數據的速度能盡可能的快，因此數據庫系統的設計者會從查詢算法的角度進行優化。最基本的查詢算法當然是順序查找，這種復雜度為 O(n) 的算法在數據量很大時顯然是糟糕的，好在計算機科學的發展提供了很多更優秀的查找算法，例如二分查找、二叉樹查找等。如果稍微分析一下會發現，每種查找算法都只能應用于特定的數據結構之上，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用于二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構（例如，理論上不可能同時將兩列都按順序進行組織），所以，在數據之外，數據庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。

我們一起聊聊MySQL 索引的底層邏輯圖片

1.1 B-Tree

為了描述 B-Tree ，首先定義一條數據記錄為一個二元組 [key, data] ， key 為記錄的鍵值，對于不同數據記錄， key 是互不相同的；data 為數據記錄除 key 外的數據。那么 B-Tree 是滿足下列條件的數據結構：

d 為大于 1 的一個正整數，稱為 B-Tree 的度。
h 為一個正整數，稱為 B-Tree 的高度。
每個非葉子節點由 n-1 個 key 和 n 個指針組成，其中 d<=n<=2d 。
每個葉子節點最少包含一個 key 和兩個指針，最多包含 2d-1 個 key 和 2d 個指針，葉節點的指針均為 null 。
所有葉節點具有相同的深度，等于樹高 h 。
key 和指針互相間隔，節點兩端是指針。
一個節點中的 key 從左到右非遞減排列。
所有節點組成樹結構。
每個指針要么為 null ，要么指向另外一個節點。
如果某個指針在節點 node 最左邊且不為 null ，則其指向節點的所有 key 小于 v(key_1)，其中 v(key_1) 為 node 的第一個 key 的值。
如果某個指針在節點 node 最右邊且不為 null ，則其指向節點的所有 key 大于 v(key_m) ，其中 v(key_m) 為 node 的最后一個 key 的值。
如果某個指針在節點 node 的左右相鄰 key 分別是 key_i 和 key{i+1} 且不為 null ，則其指向節點的所有 key 小于 v(key{i+1}) 且大于 v(key_i) 。

如下是一個 d = 2 的 B-Tree 示意圖。

我們一起聊聊MySQL 索引的底層邏輯圖片

由于 B-Tree 的特性，在 B-Tree 中按 key 檢索數據的算法非常直觀：首先從根節點進行二分查找，如果找到則返回對應節點的 data ，否則對相應區間的指針指向的節點遞歸進行查找，直到找到節點或找到 null 指針，前者查找成功，后者查找失敗。B-Tree 上查找算法的偽代碼如下：

BTree_Search(node, key) {
    if(node == null) return null;
    foreach(node.key)
    {
        if(node.key[i] == key) return node.data[i];
        if(node.key[i] > key) return BTree_Search(point[i]->node);
    }
    return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

關于 B-Tree 有一系列有趣的性質，例如一個度為 d 的 B-Tree ，設其索引 N 個 key ，則其樹高 h 的上限為 log_d((N+1)/2) ，檢索一個 key ，其查找節點個數的漸進復雜度為 O(log_dN) 。從這點可以看出， B-Tree 是一個非常有效率的索引數據結構。

1.2 B+Tree

B-Tree 有許多變種，其中最常見的是 B+Tree ，例如 MySQL 就普遍使用 B+Tree 實現其索引結構。與 B-Tree 相比， B+Tree 有以下不同點：

每個節點的指針上限為 2d 而不是 2d+1 。
內節點不存儲 data ，只存儲 key ；葉子節點不存儲指針。

如下是一個簡單的 B+Tree 示意。

我們一起聊聊MySQL 索引的底層邏輯圖片

由于并不是所有節點都具有相同的域，因此 B+Tree 中葉節點和內節點一般大小不同。這點與 B-Tree 不同，雖然 B-Tree 中不同節點存放的 key 和指針可能數量不一致，但是每個節點的域和上限是一致的，所以在實現中 B-Tree 往往對每個節點申請同等大小的空間。一般來說， B+Tree 比 B-Tree 更適合實現外存儲索引結構，具體原因與外存儲器原理及計算機存取原理有關，將在下面討論。

1.3 帶有順序訪問指針的 B+Tree

一般在數據庫系統或文件系統中使用的 B+Tree 結構都在經典 B+Tree 的基礎上進行了優化，增加了順序訪問指針。

我們一起聊聊MySQL 索引的底層邏輯圖片

如圖所示，在 B+Tree 的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序訪問指針的 B+Tree 。做這個優化的目的是為了提高區間訪問的性能，例如圖中如果要查詢 key 為從 18 到 49 的所有數據記錄，當找到 18 后，只需順著節點和指針順序遍歷就可以一次性訪問到所有數據節點，極大提到了區間查詢效率。

1.4 為什么使用 B-Tree / B+Tree

紅黑樹等數據結構也可以用來實現索引，但是文件系統及數據庫系統普遍采用 B-/+Tree 作為索引結構，這一節將結合計算機組成原理相關知識討論 B-/+Tree 作為索引的理論基礎。一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤 I/O 消耗，相對于內存存取， I/O 存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤 I/O 操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤 I/O 的存取次數。下面先介紹內存和磁盤存取原理，然后再結合這些原理分析 B-/+Tree 作為索引的效率。

主存存取原理

目前計算機使用的主存基本都是隨機讀寫存儲器（ RAM ），現代 RAM 的結構和存取原理比較復雜，這里本文拋卻具體差別，抽象出一個十分簡單的存取模型來說明 RAM 的工作原理。

我們一起聊聊MySQL 索引的底層邏輯圖片

從抽象角度看，主存是一系列的存儲單元組成的矩陣，每個存儲單元存儲固定大小的數據。每個存儲單元有唯一的地址，現代主存的編址規則比較復雜，這里將其簡化成一個二維地址：通過一個行地址和一個列地址可以唯一定位到一個存儲單元。上圖展示了一個 4 x 4 的主存模型。主存的存取過程如下：當系統需要讀取主存時，則將地址信號放到地址總線上傳給主存，主存讀到地址信號后，解析信號并定位到指定存儲單元，然后將此存儲單元數據放到數據總線上，供其它部件讀取。寫主存的過程類似，系統將要寫入單元地址和數據分別放在地址總線和數據總線上，主存讀取兩個總線的內容，做相應的寫操作。這里可以看出，主存存取的時間僅與存取次數呈線性關系，因為不存在機械操作，兩次存取的數據的“距離”不會對時間有任何影響，例如，先取 A0 再取 A1 和先取 A0 再取 D3 的時間消耗是一樣的。

磁盤存取原理

上文說過，索引一般以文件形式存儲在磁盤上，索引檢索需要磁盤 I/O 操作。與主存不同，磁盤 I/O 存在機械運動耗費，因此磁盤 I/O 的時間消耗是巨大的。下圖是磁盤的整體結構示意圖。

我們一起聊聊MySQL 索引的底層邏輯圖片

一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉動（各個磁盤必須同步轉動）。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內容。磁頭不能轉動，但是可以沿磁盤半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）。下圖是磁盤結構的示意圖。

我們一起聊聊MySQL 索引的底層邏輯圖片

盤片被劃分成一系列同心環，圓心是盤片中心，每個同心環叫做一個磁道，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段，每個段叫做一個扇區，每個扇區是磁盤的最小存儲單元。為了簡單起見，我們下面假設磁盤只有一個盤片和一個磁頭。當需要從磁盤讀取數據時，系統會將數據邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數據在哪個磁道，哪個扇區。為了讀取這個扇區的數據，需要將磁頭放到這個扇區上方，為了實現這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然后磁盤旋轉將目標扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。

局部性原理與磁盤預讀

由于存儲介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤 I/O 。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節，磁盤也會從這個位置開始，順序向后讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：當一個數據被用到時，其附近的數據也通常會馬上被使用。程序運行期間所需要的數據通常比較集中。由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間），因此對于具有局部性的程序來說，預讀可以提高 I/O 效率。預讀的長度一般為頁（ page ）的整倍數。頁是計算機管理存儲器的邏輯塊，硬件及操作系統往往將主存和磁盤存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁（在許多操作系統中，頁得大小通常為 4k ），主存和磁盤以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁盤發出讀盤信號，磁盤會找到數據的起始位置并向后連續讀取一頁或幾頁載入內存中，然后異常返回，程序繼續運行。

B-/+Tree 索引的性能分析

到這里終于可以分析 B-/+Tree 索引的性能了。上面說過一般使用磁盤 I/O 次數評價索引結構的優劣。先從 B-Tree 分析，根據 B-Tree 的定義，可知檢索一次最多需要訪問 h 個節點。數據庫系統的設計者巧妙利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣每個節點只需要一次 I/O 就可以完全載入。為了達到這個目的，在實際實現 B-Tree 還需要使用如下技巧：每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個 node 只需一次 I/O 。B-Tree 中一次檢索最多需要 h-1 次 I/O（根節點常駐內存），漸進復雜度為 O(h) = O(log_dN) 。一般實際應用中，出度d是非常大的數字，通常超過 100 ，因此 h 非常小（通常不超過 3 ）。綜上所述，用 B-Tree 作為索引結構效率是非常高的。而紅黑樹這種結構， h 明顯要深的多。由于邏輯上很近的節點（父子）物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為 O(h) ，效率明顯比 B-Tree 差很多。上面還說過， B+Tree 更適合外存索引，原因和內節點出度 d 有關。從上面分析可以看到， d 越大索引的性能越好，而出度的上限取決于節點內 key 和 data 的大小：d_{max} = floor(pagesize / (keysize + datasize + pointsize)) 。floor 表示向下取整。由于 B+Tree 內節點去掉了 data 域，因此可以擁有更大的出度，擁有更好的性能。

MySQL 的實現

在 MySQL 中，索引屬于存儲引擎級別的概念，不同存儲引擎對索引的實現方式是不同的，本文主要討論 MyISAM 和 InnoDB 兩個存儲引擎的索引實現方式。

2.1 MyISAM 索引實現

MyISAM 引擎使用 B+Tree 作為索引結構，葉節點的 data 域存放的是數據記錄的地址。下圖是 MyISAM 索引的原理圖：

我們一起聊聊MySQL 索引的底層邏輯圖片

這里設表一共有三列，假設我們以 Col1 為主鍵，則上圖是一個 MyISAM 表的主索引（ Primary key ）示意。可以看出 MyISAM 的索引文件僅僅保存數據記錄的地址。在 MyISAM 中，主索引和輔助索引（ Secondary key ）在結構上沒有任何區別，只是主索引要求 key 是唯一的，而輔助索引的 key 可以重復。如果我們在 Col2 上建立一個輔助索引，則此索引的結構如下圖所示：

我們一起聊聊MySQL 索引的底層邏輯圖片

同樣也是一顆 B+Tree ， data 域保存數據記錄的地址。因此， MyISAM 中索引檢索的算法為首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，則取出其data域的值，然后以 data 域的值為地址，讀取相應數據記錄。MyISAM 的索引方式也叫做“非聚集”的，之所以這么稱呼是為了與 InnoDB 的聚集索引區分。

2.2 InnoDB 索引實現

雖然 InnoDB 也使用 B+Tree 作為索引結構，但具體實現方式卻與 MyISAM 截然不同。第一個重大區別是 InnoDB 的數據文件本身就是索引文件。從上文知道， MyISAM 索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。而在 InnoDB 中，表數據文件本身就是按 B+Tree 組織的一個索引結構，這棵樹的葉節點 data 域保存了完整的數據記錄。這個索引的 key 是數據表的主鍵，因此 InnoDB 表數據文件本身就是主索引。

我們一起聊聊MySQL 索引的底層邏輯圖片

上圖是 InnoDB 主索引（同時也是數據文件）的示意圖，可以看到葉節點包含了完整的數據記錄。這種索引叫做聚集索引。因為 InnoDB 的數據文件本身要按主鍵聚集，所以 InnoDB 要求表必須有主鍵（ MyISAM 可以沒有），如果沒有顯式指定，則 MySQL 系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則 MySQL 自動為 InnoDB 表生成一個隱含字段作為主鍵，這個字段長度為 6 個字節，類型為長整形。第二個與 MyISAM 索引的不同是 InnoDB 的輔助索引 data 域存儲相應記錄主鍵的值而不是地址。換句話說， InnoDB 的所有輔助索引都引用主鍵作為 data 域。例如，下圖為定義在 Col3 上的一個輔助索引：

我們一起聊聊MySQL 索引的底層邏輯圖片

這里以英文字符的 ASCII 碼作為比較準則。聚集索引這種實現方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。了解不同存儲引擎的索引實現方式對于正確使用和優化索引都非常有幫助，例如知道了 InnoDB 的索引實現后，就很容易明白為什么不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調的字段作為主鍵在 InnoDB 中不是個好主意，因為 InnoDB 數據文件本身是一顆 B+Tree ，非單調的主鍵會造成在插入新記錄時數據文件為了維持 B+Tree 的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。

總結

本文以 MySQL 數據庫為研究對象，討論與數據庫索引相關的一些話題。特別需要說明的是， MySQL 支持諸多存儲引擎，而各種存儲引擎對索引的支持也各不相同，因此 MySQL 數據庫支持多種索引類型，如 B-Tree 索引，哈希索引，全文索引等等。為了避免混亂，將只關注于 B-Tree 索引，因為這是平常使用 MySQL 時主要打交道的索引。

參考文獻

[1] Baron Scbwartz 等著，王小東等譯；高性能 MySQL（High Performance MySQL）；電子工業出版社，2010 [2] Michael Kofler 著，楊曉云等譯；MySQL5權威指南（The Definitive Guide to MySQL5）；人民郵電出版社，2006 [3] 姜承堯著；MySQL 技術內幕-InnoDB 存儲引擎；機械工業出版社，2011