B+樹在數據庫中的應用

{

為什么使用B+樹?言簡意賅，就是因為：

1.文件很大，不可能全部存儲在內存中，故要存儲到磁盤上

2.索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數(為什么使用B-/+Tree，還跟磁盤存取原理有關。)

3.局部性原理與磁盤預讀，預讀的長度一般為頁(page)的整倍數，(在許多操作系統中，頁得大小通常為4k)

4.數據庫系統巧妙利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣每個節點只需要一次I/O就可以完全載入，(由于節點中有兩個數組，所以地址連續)。而紅黑樹這種結構，h明顯要深的多。由于邏輯上很近的節點(父子)物理上可能很遠，無法利用局部性

InnoDB 與 MyISAM 結構上的區別

1.InnoDB的主鍵索引 ，MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。而在InnoDB中，表數據文件本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域保存了完整的數據記錄。這個索引的key是數據表的主鍵，因此InnoDB表數據文件本身就是主索引，所以必須有主鍵，如果沒有顯示定義，自動為生成一個隱含字段作為主鍵，這個字段長度為6個字節，類型為長整形2.InnoDB的輔助索引(Secondary Index， 也就是非主鍵索引)也會包含主鍵列，比如名字建立索引，內部節點 會包含名字，葉子節點會包含該名字對應的主鍵的值，如果主鍵定義的比較大，其他索引也將很大3.MyISAM引擎使用B+Tree作為索引結構，索引文件葉節點的data域存放的是數據記錄的地址，指向數據文件中對應的值，每個節點只有該索引列的值

4.MyISAM主索引和輔助索引(Secondary key)在結構上沒有任何區別，只是主索引要求key是唯一的，輔助索引可以重復，

(由于MyISAM輔助索引在葉子節點上存儲的是數據記錄的地址，和主鍵索引一樣，所以相對于B+的InnoDB可通過輔助索引

快速找到所有的數據，而不需要再遍歷一邊主鍵索引，所以適用于OLAP)

InnoDB索引和MyISAM索引的區別：

一是主索引的區別，InnoDB的數據文件本身就是索引文件。而MyISAM的索引和數據是分開的。

二是輔助索引的區別：InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒有多大區別。

}

1. 索引在數據庫中的作用

在數據庫系統的使用過程當中，數據的查詢是使用最頻繁的一種數據操作。

最基本的查詢算法當然是順序查找(linear search)，遍歷表然后逐行匹配行值是否等于待查找的關鍵字，其時間復雜度為O(n)。但時間復雜度為O(n)的算法規模小的表，負載輕的數據庫，也能有好的性能。 但是數據增大的時候，時間復雜度為O(n)的算法顯然是糟糕的，性能就很快下降了。

好在計算機科學的發展提供了很多更優秀的查找算法，例如二分查找(binary search)、二叉樹查找(binary tree search)等。如果稍微分析一下會發現，每種查找算法都只能應用于特定的數據結構之上，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用于二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構(例如，理論上不可能同時將兩列都按順序進行組織)，所以，在數據之外，數據庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。

索引是對數據庫表 中一個或多個列的值進行排序的結構。與在表 中搜索所有的行相比，索引用指針 指向存儲在表中指定列的數據值，然后根據指定的次序排列這些指針，有助于更快地獲取信息。通常情 況下 ，只有當經常查詢索引列中的數據時 ，才需要在表上創建索引。索引將占用磁盤空間，并且影響數 據更新的速度。但是在多數情況下 ，索引所帶來的數據檢索速度優勢大大超過它的不足之處。

2. B+樹在數據庫索引中的應用

目前大部分數據庫系統及文件系統都采用B-Tree或其變種B+Tree作為索引結構

1)在數據庫索引的應用

在數據庫索引的應用中，B+樹按照下列方式進行組織 ：

① 葉結點的組織方式 。B+樹的查找鍵 是數據文件的主鍵 ，且索引是稠密的。也就是說 ，葉結點 中為數據文件的第一個記錄設有一個鍵、指針對 ，該數據文件可以按主鍵排序，也可以不按主鍵排序 ;數據文件按主鍵排序，且 B +樹是稀疏索引 ， 在葉結點中為數據文件的每一個塊設有一個鍵、指針對 ;數據文件不按鍵屬性排序 ，且該屬性是 B +樹 的查找鍵 ， 葉結點中為數據文件里出現的每個屬性K設有一個鍵 、 指針對 ， 其中指針執行排序鍵值為 K的 記錄中的第一個。

② 非葉結點 的組織方式。B+樹 中的非葉結點形成 了葉結點上的一個多級稀疏索引。 每個非葉結點中至少有ceil( m/2 ) 個指針 ， 至多有 m 個指針 。

2)B+樹索引的插入和刪除

①在向數據庫中插入新的數據時，同時也需要向數據庫索引中插入相應的索引鍵值 ，則需要向 B+樹 中插入新的鍵值。即上面我們提到的B-樹插入算法。

②當從數據庫中刪除數據時，同時也需要從數據庫索引中刪除相應的索引鍵值 ，則需要從 B+樹 中刪 除該鍵值 。即B-樹刪除算法

#p#

為什么使用B-Tree(B+Tree)

二叉查找樹進化品種的紅黑樹等數據結構也可以用來實現索引，但是文件系統及數據庫系統普遍采用B-/+Tree作為索引結構。

一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。為什么使用B-/+Tree，還跟磁盤存取原理有關。

局部性原理與磁盤預讀

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

• 當一個數據被用到時，其附近的數據也通常會馬上被使用。
• 程序運行期間所需要的數據通常比較集中。

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

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

我們上面分析B-/+Tree檢索一次最多需要訪問節點：

h =

數據庫系統巧妙利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現B- Tree還需要使用如下技巧：

每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O(根節點常駐內存)，漸進復雜度為O(h)=O(logmN)。一般實際應用中，m是非常大的數字，通常超過100，因此h非常小(通常不超過3)。

綜上所述，用B-Tree作為索引結構效率是非常高的。

而紅黑樹這種結構，h明顯要深的多。由于邏輯上很近的節點(父子)物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多。

MySQL的B-Tree索引(技術上說B+Tree)

在 MySQL 中，主要有四種類型的索引，分別為： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我們主要分析B-Tree 索引。

B-Tree 索引是 MySQL 數據庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引，而且只支持索引單個 AUTO_INCREMENT 列。

不僅僅在 MySQL 中是如此，實際上在其他的很多數據庫管理系統中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為 B-Tree 索引的存儲結構在數據庫的數據檢索中有非常優異的表現。

一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結構來存儲的，也就是所有實際需要的數據都存放于 Tree 的 Leaf Node(葉子節點) ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引。當然，可能各種數據庫(或 MySQL 的各種存儲引擎)在存放自己的 B-Tree 索引的時候會對存儲結構稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結構實際上是 B+Tree，也就是在 B-Tree 數據結構的基礎上做了很小的改造，在每一個Leaf Node 上面出了存放索引鍵的相關信息之外，還存儲了指向與該 Leaf Node 相鄰的后一個 LeafNode 的指針信息(增加了順序訪問指針)，這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。

#p#

下面主要討論MyISAM和InnoDB兩個存儲引擎的索引實現方式：

1. MyISAM索引實現：

1)主鍵索引：

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

 

(圖myisam1)

這里設表一共有三列，假設我們以Col1為主鍵，圖myisam1是一個MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件僅僅保存數據記錄的地址。

2)輔助索引(Secondary key)

在MyISAM中，主索引和輔助索引(Secondary key)在結構上沒有任何區別，只是主索引要求key是唯一的，而輔助索引的key可以重復。如果我們在Col2上建立一個輔助索引，則此索引的結構如下圖所示：

 

同樣也是一顆B+Tree，data域保存數據記錄的地址。因此，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應數據記錄。

MyISAM的索引方式也叫做“非聚集”的，之所以這么稱呼是為了與InnoDB的聚集索引區分。

2. InnoDB索引實現

然InnoDB也使用B+Tree作為索引結構，但具體實現方式卻與MyISAM截然不同.

1)主鍵索引：

MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。而在InnoDB中，表數據文件本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域保存了完整的數據記錄。這個索引的key是數據表的主鍵，因此InnoDB表數據文件本身就是主索引。

 

(圖inndb主鍵索引)

(圖inndb主鍵索引)是InnoDB主索引(同時也是數據文件)的示意圖，可以看到葉節點包含了完整的數據記錄。這種索引叫做聚集索引。因為InnoDB的數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵(MyISAM可以沒有)，如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含字段作為主鍵，這個字段長度為6個字節，類型為長整形。

2). InnoDB的輔助索引

InnoDB的所有輔助索引都引用主鍵作為data域。例如，下圖為定義在Col3上的一個輔助索引：

 

InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一種非常快速的主鍵查找性能。不過，它的輔助索引(Secondary Index， 也就是非主鍵索引)也會包含主鍵列，所以，如果主鍵定義的比較大，其他索引也將很大。如果想在表上定義 、很多索引，則爭取盡量把主鍵定義得小一些。InnoDB 不會壓縮索引。

文字符的ASCII碼作為比較準則。聚集索引這種實現方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。

不同存儲引擎的索引實現方式對于正確使用和優化索引都非常有幫助，例如知道了InnoDB的索引實現后，就很容易明白為什么不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調的字段作為主鍵在InnoDB中不是個好主意，因為InnoDB數據文件本身是一顆B+Tree，非單調的主鍵會造成在插入新記錄時數據文件為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。

一是主索引的區別，InnoDB的數據文件本身就是索引文件。而MyISAM的索引和數據是分開的。

二是輔助索引的區別：InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒有多大區別。