數據庫索引的原理是什麼？

本文導航

1、首頁2、數據庫索引的原理-23、數據庫索引的原理-3

現定在的信息社會，大量的數據信息被使用，在數據庫中運用索引可快速訪問數據庫表中的特定信息，所以了解數據庫索引的原理變得尤為重要。

中小企業MIS系統的管理基本上由兩大部份組成，一是前台的可視化操作，二是後台的數據庫管理。網管對前台的管理和維護工作包括保障網絡鏈路通暢、處理MIS終端的突發事件以及對操作員的管理、培訓等，這是網管們日常做得最多、最辛苦的功課;然而MIS系統架構中同等重要的針對數據庫的管理、維護和優化工作，現實中似乎並沒有得到網管朋友的足夠重視，看起來這都是程序員的事，事實上，一個網管如果能在MIS設計期間就數據表的規范化、表索引優化、容量設計、事務處理等諸多方面與程序員進行卓有成效的溝通和協作，那麼日常的前台管理工作將會變得大為輕松,因為在某種意義上，數據庫管理系統就相當於操作系統，在系統中占有同樣重要的位置。

這正是SQL SERVER等數據庫管理系統和dBASEX、ACCESS等數據庫文件系統的本質區別，所以，對數據庫管理系統操作能力的強弱在某種程度上也折射出了網管的水平——個人認為，稱得上優秀的Admin,至少應該是一個稱職的DBA(數據庫管理員)。

下面以SQL SERVER(下稱 SQLS)為例，將數據庫管理中難於理解的“索引原理”問題給各位朋友作一個深入淺出的介紹。其他的數據庫管理系統如Oracle、Sybase等，朋友們可以融會貫通，舉一反三。

一、數據表的基本結構

建立數據庫的目的是管理大量數據，而建立索引的目的就是提高數據檢索效率，改善數據庫工作性能，提高數據訪問速度。對於索引，我們要知其然，更要知其所以然，關鍵在於認識索引的工作原理，才能更好的管理索引。

為認識索引工作原理，首先有必要對數據表的基本結構作一次全面的復習。

SQLS當一個新表被創建之時，系統將在磁盤中分配一段以8K為單位的連續空間，當字段的值從內存寫入磁盤時，就在這一既定空間隨機保存，當一個8K用完的時候，SQLS指針會自動分配一個8K的空間。這裡，每個8K空間被稱為一個數據頁(Page)，又名頁面或數據頁面，並分配從0-7的頁號,每個文件的第0頁記錄引導信息，叫文件頭(File header);每8個數據頁(64K)的組合形成擴展區(Extent)，稱為擴展。全部數據頁的組合形成堆(Heap)。

SQLS規定行不能跨越數據頁，所以，每行記錄的最大數據量只能為8K。這就是char和varchar這兩種字符串類型容量要限制在8K以內的原因，存儲超過8K的數據應使用text類型，實際上，text類型的字段值不能直接錄入和保存，它只是存儲一個指針，指向由若干8K的文本數據頁所組成的擴展區，真正的數據正是放在這些數據頁中。

頁面有空間頁面和數據頁面之分。

當一個擴展區的8個數據頁中既包含了空間頁面又包括了數據或索引頁面時，稱為混合擴展(Mixed Extent),每張表都以混合擴展開始;反之，稱為一致擴展(Uniform Extent)，專門保存數據及索引信息。

表被創建之時，SQLS在混合擴展中為其分配至少一個數據頁面，隨著數據量的增長，SQLS可即時在混合擴展中分配出7個頁面，當數據超過8個頁面時，則從一致擴展中分配數據頁面。

空間頁面專門負責數據空間的分配和管理，包括：PFS頁面(Page free space)：記錄一個頁面是否已分配、位於混合擴展還是一致擴展以及頁面上還有多少可用空間等信息;GAM頁面(Global allocation map)和SGAM頁面(Secodary global allocation map)：用來記錄空閒的擴展或含有空閒頁面的混合擴展的位置。SQLS綜合利用這三種類型的頁面文件在必要時為數據表創建新空間;

數據頁或索引頁則專門保存數據及索引信息，SQLS使用4種類型的數據頁面來管理表或索引：它們是IAM頁、數據頁、文本/圖像頁和索引頁。

在WINDOWS中，我們對文件執行的每一步操作，在磁盤上的物理位置只有系統(system)才知道;SQL SERVER沿襲了這種工作方式，在插入數據的過程中，不但每個字段值在數據頁面中的保存位置是隨機的，而且每個數據頁面在“堆”中的排列位置也只有系統(system)才知道。

這是為什麼呢?眾所周知，OS之所以能管理DISK，是因為在系統啟動時首先加載了文件分配表：FAT(File Allocation Table)，正是由它管理文件系統並記錄對文件的一切操作，系統才得以正常運行;同理，作為管理系統級的SQL SERVER,也有這樣一張類似FAT的表存在，它就是索引分布映像頁：IAM(Index Allocation Map)。

IAM的存在，使SQLS對數據表的物理管理有了可能。

IAM頁從混合擴展中分配，記錄了8個初始頁面的位置和該擴展區的位置，每個IAM頁面能管理512,000個數據頁面，如果數據量太大，SQLS也可以增加更多的IAM頁，可以位於文件的任何位置。第一個IAM頁被稱為FirstIAM,其中記錄了以後的IAM頁的位置。

數據頁和文本/圖像頁互反，前者保存非文本/圖像類型的數據，因為它們都不超過8K的容量，後者則只保存超過8K容量的文本或圖像類型數據。而索引頁顧名思義，保存的是與索引結構相關的數據信息。了解頁面的問題有助我們下一步准確理解SQLS維護索引的方式，如頁拆分、填充因子等。

二、索引的基本概念

索引是一種特殊類型的數據庫對象，它與表有著密切的聯系。

索引是為檢索而存在的。如一些書籍的末尾就專門附有索引，指明了某個關鍵字在正文中的出現的頁碼位置，方便我們查找，但大多數的書籍只有目錄，目錄不是索引，只是書中內容的排序，並不提供真正的檢索功能。可見建立索引要單獨占用空間;索引也並不是必須要建立的，它們只是為更好、更快的檢索和定位關鍵字而存在。

再進一步說，我們要在圖書館中查閱圖書，該怎麼辦呢?圖書館的前台有很多叫做索引卡片櫃的小櫃子，裡面分了若干的類別供我們檢索圖書，比如你可以用書名的筆畫順序或者拼音順序作為查找的依據，你還可以從作者名的筆畫順序或拼音順序去查詢想要的圖書，反正有許多檢索方式，但有一點很明白，書庫中的書並沒有按照這些卡片櫃中的順序排列——雖然理論上可以這樣做，事實上，所有圖書的脊背上都人工的粘貼了一個特定的編號①，它們是以這個順序在排列。索引卡片中並沒有指明這本書擺放在書庫中的第幾個書架的第幾本，僅僅指明了這個特定的編號。管理員則根據這一編號將請求的圖書返回到讀者手中。這是很形象的例子，以下的講解將會反復用到它。

SQLS在安裝完成之後，安裝程序會自動創建master、model、tempdb等幾個特殊的系統數據庫，其中master是SQLS的主數據庫，用於保存和管理其它系統數據庫、用戶數據庫以及SQLS的系統信息，它在SQLS中的地位與WINDOWS下的注冊表相當。

master中有一個名為sysindexes的系統表，專門管理索引。SQLS查詢數據表的操作都必須用到它，毫無疑義，它是本文主角之一。

查看一張表的索引屬性，可以在查詢分析器中使用以下命令：select * from sysindexes where id=object_id(‘tablename’) ;而要查看表的索引所占空間的大小，可以使用系統存儲過程命令：sp_spaceused tablename，其中參數tablename為被索引的表名。

三、平衡樹

如果你通過書後的索引知道了一個關鍵字所在的頁碼，你有可能通過隨機的翻尋，最終到達正確的頁碼。但更科學更快捷的方法是：首先把書翻到大概二分之一的位置，如果要找的頁碼比該頁的頁碼小，就把書向前翻到四分之一處，否則，就把書向後翻到四分之三的地方，依此類推，把書頁續分成更小的部分，直至正確的頁碼。這叫“兩分法”，微軟在官方教程MOC裡另有一種說法：叫B樹(B-Tree，Balance Tree)，即平衡樹。

一個表索引由若干頁面組成，這些頁面構成了一個樹形結構。B樹由“根”(root)開始，稱為根級節點，它通過指向另外兩個頁，把一個表的記錄從邏輯上分成兩個部分：“枝”—--非葉級節點(Non-Leaf Level);而非葉級節點又分別指向更小的部分：“葉”——葉級節點(Leaf Level)。根節點、非葉級節點和葉級節點都位於索引頁中，統稱為索引節點，屬於索引頁的范籌。這些“枝”、“葉”最終指向了具體的數據頁(Page)。在根級節點和葉級節點之間的葉又叫數據中間頁。

“根”(root)對應了sysindexes表的Root字段，其中記載了非葉級節點的物理位置(即指針);非葉級節點位於根節點和葉節點之間，記載了指向葉級節點的指針;而葉級節點則最終指向數據頁。這就是“平衡樹”。