算法和數據結構～Sqlserver索引使用的B樹 - lori－IT工程師數位筆記本

文章出處

B樹相關概念

在B-樹中查找給定關鍵字的方法是，首先把根結點取來，在根結點所包含的關鍵字K1,…,Kn查找給定的關鍵字（可用順序查找或二分查找法），若找到等于給定值的關鍵字，則查找成功；否則，一定可以確定要查找的關鍵字在Ki與Ki+1之間，Pi為指向子樹根節點的指針，此時取指針Pi所指的結點繼續查找，直至找到，或指針Pi為空時查找失敗。

時間復雜度

動態查找樹主要有：二叉查找樹（Binary Search Tree），平衡二叉查找樹（Balanced Binary Search Tree），紅黑樹(Red-Black Tree )，B-tree/B⁺-tree/ B^*-tree (B~Tree)。前三者是典型的二叉查找樹結構，其查找的時間復雜度

O(log₂N)

與樹的深度相關，那么降低樹的深度自然會提高查找效率。

在SQLSERVER里的表現

我們都知道sqlserver數據行的存儲結構有兩種:堆（heap）和B樹（binary二叉樹）。學過數據結構的人都知道，二叉樹的優點是：快速使用二分法找到數據，數據頁面使用雙向鏈表首尾相連。再介紹一下數據結構中的堆（heap）。堆中的數據沒有任何順序，數據頁面也不會首尾相連。那怎么在堆中查找數據呢? 堆的結構及IAM結構如下：

堆表只依靠表里的IAM頁（索引分配映射頁）將堆的頁面聯系在一起，IAM中記錄了頁面編號和頁面位置。由此可以通過IAM掃描數據。
      1.很多書中都講到sqlserver數據行的存儲結構有兩種:堆（heap）和B樹（binary二叉樹）。而我覺得sqlserver數據頁的存儲結構有兩種：堆（heap）和B樹（binary二叉樹）。
      2.數據都存在頁面中，sqlserver頁面有兩種類型：數據頁和索引頁。索引頁都是按照B樹結構存儲的。
      那么重點來了:
      不管是聚集索引，還是非聚集索引，索引數據都存放在索引頁中。
      表中如果有聚合索引，那么數據全部存儲在索引頁中。
      表中如果只有有非聚合索引，那么數據存在堆頁（也就是實際的數據行），但是索引數據存儲在索引頁中。
      表中如果既有聚集索引，也有非聚集索引，那么數據和索引都存放在索引頁中。
      B樹結構中，每一個節點就是一個頁面，B樹里會有一頁：root page（亦即是根節點），非聚集索引和聚集索引都是一樣的。
     下面開始步入正軌介紹索引：

聚集索引:

有人會問為什么一張表只能有一個聚集索引，簡單來說因為表只能以一種順序排列在磁盤中，所以表只能有一個聚集索引。而非聚集索引能有好幾個。
聚集索引因為數據全部存放在索引頁中，所以順著聚集索引就可以查到數據。聚集索引結構如下：

非聚集索引

1.如果非聚集索引的數據放在堆表中（表示沒有聚集索引），而非聚集索引的數據放在索引頁中。那么非聚集索引怎么查找數據呢？在非聚集索引的葉子節點（即葉子頁面）有行定位器，行定位器指向行的位置。由文件標示符、頁碼、行上的行數組成。整個指針稱為行ID(RID)。
2.如果非聚集索引的數據放在索引表中（表示有聚集索引），那怎么查找數據呢？則行定位器會指向聚集索引鍵。SQL使用非聚集索引葉子節點的指針指向的聚集索引鍵值，來查找數據。