公司內部培訓SQL Server傳統索引結構PPT分享

B樹索引的由來
1970年，由波音公司的Rudolf.Bayer和Ed.mccreight提出了一種適用于外查找的樹，它是一種平衡的多叉樹，稱為B樹（或B-樹、B_樹）。
B的含義尚無定論，一般認為是Boeing，Bayer，balanced

下載地址

http://files.cnblogs.com/files/lyhabc/SQLServer%E4%BC%A0%E7%BB%9F%E7%B4%A2%E5%BC%95%E7%BB%93%E6%9E%84.ppt

SQL優化 講課

下載地址

http://files.cnblogs.com/files/lyhabc/SQL%E4%BC%98%E5%8C%96%E8%AE%B2%E8%AF%BE.rar

PPT有不對的地方，多多拍磚o(∩_∩)o 

索引結構

f

f

一頁只能存儲8060字節實際用戶數據

表只有一列，并且數據類型為int的話，可以存儲2015個值

f

f

f

f

f

頁拆分

一個頁裝不下所有條目，頁拆分過程：為索引分配兩個額外的頁
現有的rootpage 下降成一個葉級頁。SQL Server獲取索引頁一半數據，把這一半數據移動到一個新分配的頁面。另一個新頁則放在索引結構的頂部，成為新的rootpage，整個過程的最后一步是獲取每個葉級頁的第一個條目，并將那些條目寫入新創建的rootpage中

f

rootpage的2015行對應于中間級頁面的2015個頁，每個中間級頁面也有2015個條目，它們對應于葉級的2015個頁，最后加一個用于觸發新層級的數據行（2015 3次方+1）
在成長到超過80億多行后，才需要掃描三個索引頁

rootpage已經到了存儲極限，他不能容納2016個條目，因為那會使他超過最大允許的8060字節，因此，SQL Server會再次經歷一次“頁拆分”過程，以前的rootpage變成一個中間級頁，同時創建一個新的中間級頁。以前的rootpage分一半條目給新建的中間級頁。同時，兩個中間級頁的第一個條目都寫入新的rootpage

所以SQL Server是B*樹

f

f

空間索引

 空間數據用一個二維坐標系統定義，索引用B樹構建，而B樹是一個線性結構

f

由于幾何平面是無限的，所以不能為所有可能的二維空間都一定一個B樹

f

交換分區的原理

假設一個表只有一個字段int類型 4字節，那么

一個頁面實際數據8060字節除以4字節 得出一個頁面可以存儲2015行數據
8060/4=2015

扇出值就是2015
一個父節點可以有2015個孩子

二級
2015*2015=4060225 行
2016個頁面

三級
2015*2015*2015=8181353375 行
4060226個頁面

f

SQL Server2008數據庫技術內幕P165

BOOT PAGE里面的dbi_firstSysIndexes項指向sys.sysallocunits數據字典表

f