一、位圖索引
位圖索引(bitmap
indices)是一種專為多個鍵的簡單查詢而設計的。應用位圖索引的前提是記錄必須被按順序編号，一般從0開始。給出編号n，必須能夠很容易的找到對應的記錄，如果記錄被存放在連續的塊，可以将編号n轉換成塊編号+塊内偏移的表示以快速定位記錄位置。
位圖索引的結構
位圖索引用一個位來對應一條記錄，這便是記錄需要被編号的原因。instructor_info表如上圖，性别的值有男、女兩種，收入等級則劃分為5級，既有5種值。在給性别屬性建立位圖索引時，就會分别為male和female建立，對于male位圖來說，如果一條記錄的性别為male，則位圖上對應的位會置1，female、收入等級位圖也采用相同的做法。
位圖索引的優勢展現在根據多個鍵的查詢的時候，比如查詢where gender=’f’ and income_level=’L2’，隻需将f的bitmap和L2的bitmap取交集即可。
此外，在進行資料分析時經常需要統計符合某些條件的記錄的數量，使用bitmap也可以很友善地實作，隻需統計交集中值為1的位的數目。
删除記錄的時候會使資料序列産生間隙，但逐個移動資料消除間隙開銷很大，是以引入一個新的存在位圖(existence bitmap)，在間隙對應的位置1。新增的資料将被追加到尾部，這樣不會影響已有記錄的順序。
二、查詢處理
在從資料庫提取資料的過程中，查詢處理要做的操作有：文法分析與翻譯、優化、評估與執行。
查詢代價的度量
使用傳送磁盤塊數(number of block transfers)和搜尋磁盤次數(number of disk seeks)來衡量查詢的代價。假設磁盤子系統傳輸一個塊的資料需要tT秒，搜尋資料需要ts秒，則傳送b個塊并進行S次磁盤搜尋的操作将消耗b*tT+s*ts秒。現在磁盤的典型數值為tT =0.1毫秒，ts =4毫秒，假定磁盤塊的大小是4KB，傳輸率為40MB/秒。
通過将讀操作與寫操作區分開可以做出更精細地估算，寫操作花費的時間約為讀操作的兩倍，因為寫完資料後，磁盤系統會再次讀取該扇區以驗證寫入是否成功。
學習資料：Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan