一脏答、位圖索引
位圖索引(bitmap indices)是一種專為多個(gè)鍵的簡單查詢而設(shè)計(jì)的抱虐。應(yīng)用位圖索引的前提是記錄必須被按順序編號，一般從0開始梢夯。給出編號n言疗，必須能夠很容易的找到對應(yīng)的記錄，如果記錄被存放在連續(xù)的塊颂砸，可以將編號n轉(zhuǎn)換成塊編號+塊內(nèi)偏移的表示以快速定位記錄位置噪奄。
位圖索引的結(jié)構(gòu)
位圖索引用一個(gè)位來對應(yīng)一條記錄，這便是記錄需要被編號的原因人乓。instructor_info表如上圖勤篮，性別的值有男、女兩種色罚，收入等級則劃分為5級碰缔，既有5種值。在給性別屬性建立位圖索引時(shí)戳护，就會(huì)分別為male和female建立金抡，對于male位圖來說，如果一條記錄的性別為male腌且，則位圖上對應(yīng)的位會(huì)置1梗肝，female、收入等級位圖也采用相同的做法铺董。
位圖索引的優(yōu)勢體現(xiàn)在根據(jù)多個(gè)鍵的查詢的時(shí)候统捶，比如查詢where gender=’f’?and income_level=’L2’，只需將f的bitmap和L2的bitmap取交集即可柄粹。
此外喘鸟，在進(jìn)行數(shù)據(jù)分析時(shí)經(jīng)常需要統(tǒng)計(jì)符合某些條件的記錄的數(shù)量，使用bitmap也可以很方便地實(shí)現(xiàn)驻右，只需統(tǒng)計(jì)交集中值為1的位的數(shù)目什黑。
刪除記錄的時(shí)候會(huì)使數(shù)據(jù)序列產(chǎn)生間隙，但逐個(gè)移動(dòng)數(shù)據(jù)消除間隙開銷很大堪夭，所以引入一個(gè)新的存在位圖(existence bitmap)愕把，在間隙對應(yīng)的位置1拣凹。新增的數(shù)據(jù)將被追加到尾部，這樣不會(huì)影響已有記錄的順序恨豁。
二嚣镜、查詢處理
在從數(shù)據(jù)庫提取數(shù)據(jù)的過程中，查詢處理要做的操作有：語法分析與翻譯橘蜜、優(yōu)化菊匿、評估與執(zhí)行。
查詢代價(jià)的度量
使用傳送磁盤塊數(shù)(number of block?transfers)和搜索磁盤次數(shù)(number of disk seeks)來衡量查詢的代價(jià)计福。假設(shè)磁盤子系統(tǒng)傳輸一個(gè)塊的數(shù)據(jù)需要t
T秒跌捆，搜索數(shù)據(jù)需要ts秒，則傳送b個(gè)塊并進(jìn)行S次磁盤搜索的操作將消耗b*tT+s*ts秒∠笥保現(xiàn)在磁盤的典型數(shù)值為tT?=0.1毫秒佩厚，ts=4毫秒，假定磁盤塊的大小是4KB说订，傳輸率為40MB/秒抄瓦。
通過將讀操作與寫操作區(qū)分開可以做出更精細(xì)地估算，寫操作花費(fèi)的時(shí)間約為讀操作的兩倍陶冷，因?yàn)閷懲陻?shù)據(jù)后钙姊，磁盤系統(tǒng)會(huì)再次讀取該扇區(qū)以驗(yàn)證寫入是否成功埃叭。
學(xué)習(xí)資料：Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan
