B樹相關概念 在B-樹中查找給定關鍵字的方法是，首先把根結點取來，在根結點所包含的關鍵字K1,…,Kn查找給定的關鍵字（可用順序查找或二分查找法），若找到等於給定值的關鍵字，則查找成功；否則，一定可以確定要查找的關鍵字在Ki與Ki+1之間，Pi為指向子樹根節點的指針，此時取指針Pi所指的結點繼續查找 ...
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(log2N)
與樹的深度相關，那麼降低樹的深度自然會提高查找效率。
在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（亦即是根節點），非聚集索引和聚集索引都是一樣的。
下麵開始步入正軌介紹索引：
聚集索引:
有人會問為什麼一張表只能有一個聚集索引，簡單來說因為表只能以一種順序排列在磁碟中，所以表只能有一個聚集索引。而非聚集索引能有好幾個。
聚集索引因為數據全部存放在索引頁中，所以順著聚集索引就可以查到數據。聚集索引結構如下：
