當前位置：首頁 > 运维知识 > 数据库 >内容正文

数据库

数据库索引：位图索引

發布時間：2024/8/1 数据库 35 豆豆

生活随笔收集整理的這篇文章主要介紹了数据库索引：位图索引小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

位圖索引主要針對大量相同值的列而創建的索引。(例如：性別), 位圖索引相對于傳統的B樹索引，在葉子節點上采用了完全不同的結構組織方式。傳統B樹索引將每一行記錄保存為一個葉子節點，上面記錄對應的索引列取值和行rowid信息。而位圖索引將每個可能的索引取值組織為一個葉子節點。每個位圖索引的葉子節點上，記錄著索引鍵值、該索引鍵值的起始截止rowid和一個位圖向量串。從本質上將，位圖索引通過一個bit位來記錄一個數據行是否存在對應鍵值。這種方式存儲數據,相對于BTree索引,占用的空間非常小,創建和使用非常快. 這樣做對比傳統的B樹索引空間節省高。而且可以借助計算機位圖運算的快速特性來提高索引結果利用率。

1 基本概念

位圖索引(bitmap index)技術是一類特殊的數據庫索引技術，其索引使用bit數組（或稱bitmap、bit set、bit string、bit vector）進行存儲與計算操作。

1.1. 什么是位圖索引？

位圖索引是從oracle 7.3版本開始引入的。目前oracle企業版和個人版都支持位圖索引，但是標準版不支持。位圖索引是這樣一種結構，其中用一個索引鍵條目存儲指向多行的指針，這與B樹結構不同，在b樹結構中，索引鍵和表中的行存在著對應關系。在位圖索引中，可能只有很少的索引條目，每個索引條目指向多行，而在傳統的B*樹中，一個索引條目就指向一行那么什么是位圖索引呢？（借用網絡的例子講解）

2. 表現形式

有張表名為table的表，由三列組成，分別是姓名、性別和婚姻狀況，其中性別只有男和女兩項，婚姻狀況由已婚、未婚、離婚這三項，該表共有100w個記錄。現在有這樣的查詢：

select * from table where Gender=‘男’ and Marital=“未婚”; 姓名(Name)性別(Gender)婚姻狀況(Marital)

張三	男	已婚
李四	女	已婚
王五	男	未婚
趙六	女	離婚
孫七	女	未婚

不使用索引

不使用索引時，數據庫只能一行行掃描所有記錄，然后判斷該記錄是否滿足查詢條件。

B樹索引

對于性別，可取值的范圍只有’男’,‘女’，并且男和女可能各站該表的50%的數據，這時添加B樹索引還是需要取出一半的數據，因此完全沒有必要。相反，如果某個字段的取值范圍很廣，幾乎沒有重復，比如身份證號，此時使用B樹索引較為合適。事實上，當取出的行數據占用表中大部分的數據時，即使添加了B樹索引，數據庫如oracle、mysql也不會使用B樹索引，很有可能還是一行行全部掃描。

位圖索引

位圖索引創建了之后，生成是位圖數據可以這么理解，比如，男女兩種，然后一共八條數據，那么就生產兩個字符串，一個代表男，一個代表女，字符串長度為數據的總數量，字符串的值：第一位（如果第一條數據是男那么就是1，如果不是就0），第二位，第三位，往后都是這樣。由此就生成了長度為總數量，只包含01的字符串，通過這個字符串就能知道第幾條數據是男，第幾條不是男，同理，另外一條代表女的字符串也一樣，是女的就1，不是女的就0。

如果用戶查詢的列的基數非常的小，即只有的幾個固定值，如性別、婚姻狀況、行政區等等。要為這些基數值比較小的列建索引，就需要建立位圖索引。

對于性別這個列，位圖索引形成兩個向量，男向量為10100…，向量的每一位表示該行是否是男，如果是則位1，否為0，同理，女向量位01011。

RowId12345…

男	1	0	1	0	0
女	0	1	0	1	1

對于婚姻狀況這一列，位圖索引生成三個向量，已婚為11000…，未婚為00100…，離婚為00010…。

RowId12345…

已婚	1	1	0	0	0
未婚	0	0	1	0	1
離婚	0	0	0	1	0

當我們使用查詢語句“select * from table where Gender=‘男’ and Marital=“未婚”;”的時候首先取出男向量10100…，然后取出未婚向量00100…，將兩個向量做and操作，這時生成新向量00100…，可以發現第三位為1，表示該表的第三行數據就是我們需要查詢的結果。

RowId12345

男	1	0	1	0	0
and
未婚	0	0	1	0	1
結果	0	0	1	0	0

3. 位圖索引的創建

創建語法很簡單,就是在普通索引創建的語法中index前加關鍵字bitmap即可,例如:

create bitmap index emp_job_bitmap_idx on emp(job);

4. 位圖索引的原理

索引塊的一個索引行中存儲鍵值、起止Rowid,以及這些鍵值的位置編碼,

位置編碼中的每一位表示鍵值對應的數據行的有無.位數=表的總記錄數

所需的位圖個數=索引列的不同鍵值多少,列的不同值越少,所需的位圖就越少

當根據鍵值查詢時,可以根據起始Rowid和位圖狀態,快速定位數據.

這樣與B*樹那樣直接保存rowid的區別就在于每次都要進行rowid的換算工作。

4.1. 例子說明

CREATE TABLE EMP (EMPNO NUMBER (4) PRIMARY KEY,ENAME VARCHAR2 (10),JOB VARCHAR2 (9),MGR NUMBER (4),HIREDATE DATE,SAL NUMBER (7, 2),COMM NUMBER (7, 2),DEPNO NUMBER (4) ); INSERT INTO EMP VALUES (7369,'SMITH','CLERK',7902,to_date('17-12-1980','dd-mm-yyyy'),800,null,20); INSERT INTO EMP VALUES (7499,'ALLEN','SALESMAN',7698,to_date('20-2-1981','dd-mm-yyyy'),1600,300,30); INSERT INTO EMP VALUES (7521,'WARD','SALESMAN',7698,to_date('22-2-1981','dd-mm-yyyy'),1250,500,30); INSERT INTO EMP VALUES (7566,'JONES','MANAGER',7839,to_date('2-4-1981','dd-mm-yyyy'),2975,NULL,20); INSERT INTO EMP VALUES (7654,'MARTIN','SALESMAN',7698,to_date('28-9-1981','dd-mm-yyyy'),1250,1400,30); INSERT INTO EMP VALUES (7698,'BLAKE','MANAGER',7839,to_date('1-5-1981','dd-mm-yyyy'),2850,NULL,30); INSERT INTO EMP VALUES (7782,'CLARK','MANAGER',7839,to_date('9-6-1981','dd-mm-yyyy'),2450,NULL,10); INSERT INTO EMP VALUES (7839,'KING','PRESIDENT',NULL,to_date('17-11-1981','dd-mm-yyyy'),5000,NULL,10); INSERT INTO EMP VALUES (7844,'TURNER','SALESMAN',7698,to_date('8-9-1981','dd-mm-yyyy'),1500,0,30); INSERT INTO EMP VALUES (7900,'JAMES','CLERK',7698,to_date('3-12-1981','dd-mm-yyyy'),950,NULL,30); INSERT INTO EMP VALUES (7902,'FORD','ANALYST',7566,to_date('3-12-1981','dd-mm-yyyy'),3000,NULL,20); INSERT INTO EMP VALUES (7934,'MILLER','CLERK',7782,to_date('23-1-1982','dd-mm-yyyy'),1300,NULL,10); select distinct "JOB" from emp

create bitmap index emp_job_bitmap_idx on emp(job); SELECT EMPNO,ENAME,SAL FROM EMP WHERE JOB = 'SALESMAN';

在該索引圖中，共用5 類JOB，每類JOB 對應14 個比特位（對應14 行記錄），其中某行的在該列的值與JOB 值對應則使用比特1 表示，如JOB = ‘CLERK’，第一行在該列對應的值是CLERK，就用比特1表示。否則用比特0表示，其他JOB類類似。

SELECT EMPNO,ENAME,SAL FROM EMP WHERE JOB = 'SALESMAN'

通過位圖索引掃描JOB=‘CLERK’對應的位圖記錄，找到值為1 的行記錄，即找到需要查找數據。

上述查詢語句的目的是在EMP表中查詢工作崗位是SALESMAN的員工的員工號，姓名和薪水，此時假設已經在EMP表的JOB列建立了位圖索引，其結構如下圖所示。

(驗證了每次都要進行rowid的換算工作)

4.2. 位圖索引與數據DML鎖定

Bitmap測試

用實驗說明為什么位圖索引不適合OLTP，比較適合OLAP。即：DML操作比較多的表不適合使用位圖索引。

OLTP與OLAP是什么？： https://blog.csdn.net/joshho/article/details/117357700

以上面的EMP表為例，我們已經在該表的JOB字段建立了位圖索引

select distinct sid from v$mystat;UPDATE EMP SET JOB='CLERK' WHERE ENAME='ALLEN';

select distinct sid from v$mystat;UPDATE EMP SET JOB='SALESMAN' WHERE ENAME='SMITH';

select * from v$lock where sid in(10,128) order by type; select sid,status,last_call_et,blocking_session from v$session where sid in(10,128);

可以看見10阻塞了128 。盡管他們修改的不是同一列。

Session1提交

Session2 阻塞解除，自動執行了

5. 位圖索引的特點

5.1 Bitmap索引的存儲空間更小

相對于B*Tree索引,位圖索引由于只存儲鍵值的起止Rowid和位圖,占用的空間非常少. bitmap的空間占用主要與以下因素相關:

表的總記錄數

索引列的鍵值多少,列的不同值越少,所需的位圖就越少.

5.2 Bitmap索引創建的速度更快

位圖索引創建時不需要排序, B*Tree索引則在創建時需要排序,定位等操作,速度要慢得多.

5.3 Bitmap索引允許鍵值為空

Bitmap索引允許鍵值為空 B*Tree索引由于不記錄空值,當基于is null的查詢時,會使用全表掃描, 而對位圖索引列進行is null查詢時,則可以使用索引.

5.4 Bitmap索引對表記錄的高效訪問

當使用count(XX),可以直接訪問索引就快速得出統計數據.

當根據位圖索引的列進行and,or或 in(x,y,…)查詢時,直接用索引的位圖進行或運算,在訪問數據之前可事先過濾數據.

5.5 Bitmap索引對批量DML操作只需進行一次索引

由于通過位圖反映數據情況,批量操作時對索引的更新速度比B*Tree索引一行一行的處理快得多.

5.6 Bitmap索引的鎖機制

對于B*Tree索引,insert操作不會鎖定其它會話的DML操作. 而位圖索引,由于用位圖反映數據,不同會話更新相同鍵值的同一位圖段,insert、update、delete相互操作都會發鎖定。

6. 什么情況下應該使用位圖索引？

位圖索引適合只有幾個固定值的列，如性別、婚姻狀況、行政區等等，而身份證號這種類型不適合用位圖索引，如果用戶查詢的列的相異基數非常的小，要為這些相異基數值比較小的列建索引，就需要建立位圖索引。

那么何謂相異基數非常的小？可以認為行集中不同項的個數除以行數應該是一個很小的數（接近0），例如，某個列（性別）可能取值為M、F、null.如果一個表中有20000條數據，那么3/20000=0.00015，那么這就算是個相異基數很小的情況，類似的，如果有100000個不同的值，與10000000條結果相比，比值是0.01，同樣也很小，也可以認為是相異基數很小的情況，都可以建立位圖索引；

這個時候有人會說使用位圖索引，因為busy只有兩個值。好，我們使用位圖索引索引busy字段！假設用戶A使用update更新某個機器的busy值，比如update table set table.busy=1 where rowid=100;，但還沒有commit，而用戶B也使用update更新另一個機器的busy值，update table set table.busy=1 where rowid=12; 這個時候用戶B怎么也更新不了，需要等待用戶A commit。

原因：用戶A更新了某個機器的busy值為1，會導致所有busy為1的機器的位圖向量發生改變，因此數據庫會將busy＝1的所有行鎖定，只有commit之后才解鎖。

7. 位圖索引的限制或者說是弊端？

位圖索引在讀密集的環境中能很好地工作，但是對于寫密集的環境則極不適合，原因在于，一個位圖索引鍵條目（可以理解為前面的男、女、未婚、已婚等）指向多行。如果一個會話修改了有索引的列的數據，那么大多數情況下，這個索引條目只想的所有行都會被鎖定。oracle無法鎖定一個位圖索引條目中的單獨一位，而是會鎖定整個位圖索引條目，倘若其他會話修改也需要更新同樣的這個位圖索引條目，就會被“關在門外”，這樣就大大影響了并發性，因為每個更新都有可能鎖定數百行，不允許并發地更新他們的位圖列；

舉個例子說明：有這樣一個字段job，記錄各個員工的職位如：dba 、java、php等等，假設我們在這個job列上建立了位圖索引。假如rowid=100的員工職業為php,rowid=120的員工職業為php;

如果會話1使用update更新某個員工的職位（job），比如update table set table.job=‘dba’ where rowid=100;，但還沒有commit，而會話2也使用update更新另一個員工的職位，update table set table.job=‘dba’ where rowid=120; 這個時候會話2怎么也更新不了，需要等待會話1 commit。

原因：會話1更新rowid=100的這個員工的職位，假如這個員工原來是php,現在改成dba,那么在commit之前，就會鎖定所有job=php和job=dba的所有行，所以當會話2嘗試更新job=dba只能等待鎖，只有commit之后才解鎖。這樣就大大影響了并發性；

8. 總結：

位圖索引是為數據倉庫（也就是查詢環境設計的），位圖索引特別不適合OLTP系統，位圖索引不適合與dml頻繁的環境，位圖索引適用于DSS系統，位圖索引不適合頻繁修改的系統，弊端是嚴重影響

并發性，因為update索引列值的時候，會鎖定新值和舊值指向的所有數據行，所以使用位圖索引需慎重。

總結

以上是生活随笔為你收集整理的数据库索引：位图索引的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。