`

bitmap索引的深入研究

SQLOracle数据结构F#Blog 
阅读更多
位图（bitmap）索引是另外一种索引类型，它的组织形式与B树索引相同，也是一棵平衡树。与B树索引的区别在于叶子节点里存放索引条目的方式不同。从前面我们知道，B树索引的叶子节点里，对于表里的每个数据行，如果被索引列的值不为空的，则会为该记录行在叶子节点里维护一个对应的索引条目。

而位图索引则不是这样，其叶子节点里存放的索引条目如下图所示。

      假设某个表T里所有的记录在列C1上只具有三个值：01、02和03。在表T的C1列上创建位图索引以后，则叶子节点的内容如图9-14所示。可以看到，位图索引只有三个索引条目，也就是每个C1列的值对应一个索引条目。位图索引条目上还包含表里第一条记录所对应的ROWID以及最后一条记录所对应的ROWID。索引条目的最后一部分则是由多个bit位所组成的bitmap，每个bit位就对应一条记录。





位图索引的结构

      当发出where c1=’01’这样的SQL语句时，oracle会去搜索01所在的索引条目，然后扫描该索引条目中的bitmap里所有的bit位。第一个bit位为1，则说明第一条记录上的C1值为01，于是返回第一条记录所在的ROWID（根据该索引条目里记录的start ROWID加上行号得到该记录所在的ROWID）。第二个bit位为0，则说明第二条记录上的C1值不为01，依此类推。另外，如果索引列为空，也会在位图索引里记录，也就是将对应的bit位设置为0即可。

如果索引列上不同值的个数比较少的时候，比如对于性别列（男或女）等，则使用位图索引会比较好，因为它对空间的占用非常少（因为都是用bit位来表示表里的数据行），从而在扫描索引的时候，扫描的索引块的个数也比较少。可以试想一下，如果在列的不同值非常多的列上，比如主键列上，创建位图索引，则产生的索引条目就等于表里记录的条数，同时每个索引条目里的bitmap里，只有一个1，其它都是0。这样还不如B树索引的效率高。

如果被索引的列经常被更新的话，则不适合使用位图索引。因为当更新位图所在的列时，由于要在不同的索引条目之间修改bit位，比如将第一条记录从01变为02，则必须将01所在的索引条目的第一个bit位改为0，再将02所在的索引条目的第一个bit位改为1。因此，在更新索引条目的过程中，会锁定位图索引里多个索引条目。也就是同时只能有一个用户能够更新表T，从而降低了并发性。

      位图索引比较适合用在数据仓库系统里，不适合用在OLTP系统里。

SQL> create table t_bitmap_test as
  2  select rownum as id,trunc(dbms_random.value(1,4)) as bitcol
  3  from dba_objects where rownum<=20;
SQL> select * from t_bitmap_test;

        ID     BITCOL
---------- ----------
         1          3
         2          2
         3          1
         4          3
         5          3
         6          1
         7          1
         8          2
         9          3
        10          2
        11          3
        12          1
        13          1
        14          3
        15          2
        16          2
        17          3
        18          2
        19          1
        20          3

SQL> connect hr/hr
已连接。
SQL> alter session set events '10608 trace name context forever, level 10';

会话已更改。

SQL> create bitmap index idx_t_bitmap_test on t_bitmap_test(bitcol);

索引已创建。

SQL> alter session set events '10608 trace name context off';

会话已更改。

SQL> select object_id from user_objects where object_name='IDX_T_BITMAP_TEST';

OBJECT_ID
----------
     24499

SQL> alter session set events 'immediate trace name TREEDUMP level 24499';

会话已更改。

10608事件用来跟踪创建bitmap索引的过程。而TREEDUMP则用来转储索引的树状结构。打开转储出来的文件：
*** SESSION ID:(7.13) 2008-06-10 14:33:46.000
qerbiARwo: bitmap size is 8168
qerbiIPI default pctfree=10
qerbiIPI length=0
qerbiAllocate pfree=127 space=8168
qerbiStart first start
qerbiRop: rid=00c01ce4.0000, new=Y , key: (2):  c1 04
qerbiCmpSz notfound pctfree=10
qerbiCmpSz adjblksize=7351 length=0
qerbiRop keysize=4 maxbm=3531
kdibcoinit(3116714): srid=00c01ce4.0000
qerbiRop: rid=00c01ce4.0001, new=Y , key: (2):  c1 03
kdibcoinit(3116698): srid=00c01ce4.0001
qerbiRop: rid=00c01ce4.0002, new=Y , key: (2):  c1 02
kdibcoinit(311661c): srid=00c01ce4.0002
qerbiRop: rid=00c01ce4.0003, new=N, key: (2):  c1 04
qerbiRop: rid=00c01ce4.0004, new=N, key: (2):  c1 04
qerbiRop: rid=00c01ce4.0005, new=N, key: (2):  c1 02
qerbiRop: rid=00c01ce4.0006, new=N, key: (2):  c1 02
qerbiRop: rid=00c01ce4.0007, new=N, key: (2):  c1 03
qerbiRop: rid=00c01ce4.0008, new=N, key: (2):  c1 04
qerbiRop: rid=00c01ce4.0009, new=N, key: (2):  c1 03
qerbiRop: rid=00c01ce4.000a, new=N, key: (2):  c1 04
qerbiRop: rid=00c01ce4.000b, new=N, key: (2):  c1 02
qerbiRop: rid=00c01ce4.000c, new=N, key: (2):  c1 02
qerbiRop: rid=00c01ce4.000d, new=N, key: (2):  c1 04
qerbiRop: rid=00c01ce4.000e, new=N, key: (2):  c1 03
qerbiRop: rid=00c01ce4.000f, new=N, key: (2):  c1 03
qerbiRop: rid=00c01ce4.0010, new=N, key: (2):  c1 04
qerbiRop: rid=00c01ce4.0011, new=N, key: (2):  c1 03
qerbiRop: rid=00c01ce4.0012, new=N, key: (2):  c1 02
qerbiRop: rid=00c01ce4.0013, new=N, key: (2):  c1 04
kdibcoend(3116714): erid=00c01ce4.0017status=3
qerbiCon: key: (2):  c1 04
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 19 25 09
kdibcoend(3116698): erid=00c01ce4.0017status=3
qerbiCon: key: (2):  c1 03
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 82 c2 02
kdibcoend(311661c): erid=00c01ce4.0017status=3
qerbiCon: key: (2):  c1 02
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 64 18 04

这一段是创建bitmap索引的过程。我们先把被索引的列的值换算成十六进制：

SQL> select dump(3),dump(2),dump(1) from dual;

DUMP(3)            DUMP(2)            DUMP(1)
------------------ ------------------ ------------------
Typ=2 Len=2: 193,4 Typ=2 Len=2: 193,3 Typ=2 Len=2: 193,2

4、3、2对应的十六进制则是04、03、02。也就是上面转储部分显示的key部分的键值。
可
以看到，oracle在创建bitmap索引时，先从第一条记录开始扫描，取出第一条记录的键值（bitcol=3），也就是“qerbiRop:
rid=00c01ce4.0000, new=Y , key: (2):  c1
04”。new=Y说明这是一个新的键值，因此会对应到一个索引条目。扫描第二条记录时，发现bitcol=2，该键值也是一个新的键值，因此产生一个新
的索引条目，对应“qerbiRop: rid=00c01ce4.0001, new=Y , key: (2):  c1
03”。扫描到第三条记录时，发现bitcol=1，该键值也是一个新的键值，因此产生第三个索引条目，对应“qerbiRop:
rid=00c01ce4.0002, new=Y , key: (2):  c1 02”。
接下来扫描到的记录所对应的bitcol的值都是1、2、3中的一个，因此都不会产生新的索引条目，因此它们的new都为N。

然后扫描完表里的所有记录以后，开始创建bitmap索引条目，也就是下面的部分：
qerbiCon: key: (2):  c1 04
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 19 25 09
kdibcoend(3116698): erid=00c01ce4.0017status=3
qerbiCon: key: (2):  c1 03
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 82 c2 02
kdibcoend(311661c): erid=00c01ce4.0017status=3
qerbiCon: key: (2):  c1 02
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 64 18 04

这里的srid表示start rowid，erid表示end rowid。
可以看到总共产生了3个索引条目，其key分别为：04、03、02。
这
3个索引条目的start rowid和end
rowid的格式分两部分，中间用点隔开，点左边的表示文件号（从左边第一个字节开始的4个字节表示）和数据块号（从左边第五个字节开始的4个字节表
示），点右边表示数据块里的行号。这里的显示可以看到，这20条记录都位于相同的数据块里。这里的00c0表示文件号：

SQL> select sys.pkg_number_trans.f_hex_to_dec('c')/4 file# FROM dual;

     FILE#
----------
         3

SQL> select sys.pkg_number_trans.f_hex_to_dec('1ce4') as blk# FROM dual;

BLK#
----------------------
7396

因此这20条记录在3号数据文件的7396号数据块里。我们可以使用dbms_rowid来验证。

SQL> select distinct dbms_rowid.rowid_relative_fno(rowid) as file#,
  2  dbms_rowid.rowid_block_number(rowid) as block#
  3  from t_bitmap_test;

     FILE#     BLOCK#
---------- ----------
       3    7396

可以看到，完全符合。

每个索引条目的“bitmap : (4)”部分表示的也就是前面说到的bit位了，由1、0组成。
按照前面bitmap的理论，这20条记录所对应的三个索引条目的bitmap的样子应该为：

Key_value    start_rowid    end_rowid      理论上的bitmap         转储文件的bitmap
1          00c01ce4.0    00c01ce4.0017   00100110000110000010  ca 64 18 04
2          00c01ce4.0    00c01ce4.0017   01000001010000110100  ca 82 c2 02
3          00c01ce4.0    00c01ce4.0017   10011000101001001001  ca 19 25 09


转储文件里的bitmap如何对应到bit位呢 ？首先第一个字节的ca可以不考虑，暂时不知道第一个字节是什么意思。只考虑后三个字节。比如对于key_value=3来说，19，25，09对应的二进制为：

SQL> col c1 format a10
SQL> col c2 format a10
SQL> col c3 format a10
SQL> select sys.pkg_number_trans.f_hex_to_bin(19) as c1,
  2  sys.pkg_number_trans.f_hex_to_bin(25) as c2,
  3  sys.pkg_number_trans.f_hex_to_bin(09) as c3 from dual;

C1         C2         C3
---------- ---------- ----------
11001      100101     1001

其中不足8位的前面用0补齐，因此，C1=00011001，C2=00100101，C3=00001001
在二进制里，每个应该倒过来，从右到左排列，因此为：

C3         C2        C1
00001001   00100101   00011001


然后将它们组织为一个由多个bit位组成的bitmap的话，仍然从右到左，依次取出每个bit位，于是我们有：100110001010010010010000。我们可以把这个bit串与理论上的bitmap比较一下：
100110001010010010010000
10011000101001001001
很明显，除了最后多出来的4个0以外，其余部分完全一致。而最后多出的0并不影响这个索引条目的使用。

类似的，我们可以使用相同的方法来依次验证另外两个键值，都是符合理论值的。
数据都在一个数据块里的情况比较容易理解。如果被索引的数据分布在多个数据块里呢？

经常会有人问到，只记录start rowid和end rowid，如果被索引的记录分布在多个数据块里，那么oracle如何根据start rowed来找到bitmap里的bit=1所对应的记录的rowid呢？
创建一个表：
SQL> create table t_bitmap_2(id number,bitcol char(2000));
insert into t_bitmap_2 values(1,'A');
insert into t_bitmap_2 values(2,'A');
insert into t_bitmap_2 values(3,'A');
insert into t_bitmap_2 values(4,'B');
insert into t_bitmap_2 values(5,'A');
insert into t_bitmap_2 values(6,'A');
insert into t_bitmap_2 values(7,'B');
insert into t_bitmap_2 values(8,'A');
insert into t_bitmap_2 values(9,'A');
insert into t_bitmap_2 values(9,'A');
insert into t_bitmap_2 values(10,'B');
insert into t_bitmap_2 values(11,'B');
insert into t_bitmap_2 values(12,'B');
insert into t_bitmap_2 values(13,'B');
insert into t_bitmap_2 values(14,'B');
insert into t_bitmap_2 values(15,'B');
COMMIT;

获得这15条记录所在的数据块号：

SQL> select distinct dbms_rowid.rowid_relative_fno(rowid) as file#,
  2  dbms_rowid.rowid_block_number(rowid) as block#
  3  from t_bitmap_2;

     FILE#     BLOCK#
---------- ----------
         3       7428
         3       7429
         3       7430
         3       7431
         3       7432
         3       7433

可以知道，这15条记录分布在6个数据块里。
然后跟踪对于bitcol列上的bitmap索引的创建过程：

alter session set events '10608 trace name context forever, level 10';
create bitmap index idx_t_bitmap_2 on t_bitmap_2(bitcol);
alter session set events '10608 trace name context off';

从转储出来的文件可以看到，最终形成了两个索引条目：
……
qerbiCon: key: (2000):
41 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
……
srid=00c01d04.0 erid=00c01d08.7 bitmap: (11):  c8 06 c0 44 f8 b3 01 07 f8 56 06
……
qerbiCon: key: (2000):
42 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
……
srid=00c01d04.0 erid=00c01d09.7 bitmap: (12):  00 f8 56 06 f8 56 07 c0 a1 01 c0 44
*** 2008-06-10 11:21:08.000
很明显，这里的两个索引条目的start rowed和end rowed是不相同的。
键值为A的索引条目为：
srid=00c01d04.0 erid=00c01d08.7 bitmap: (11):  c8 06 c0 44 f8 b3 01 07 f8 56 06
其数据块从1d04到1d08，也就是：

SQL> select sys.pkg_number_trans.f_hex_to_dec('1d04') as s_blk#,
  2  sys.pkg_number_trans.f_hex_to_dec('1d08') as e_blk#
  3  from dual;

S_BLK#     E_BLK#
---------- ----------
7428    7432

而键值B的索引条目为：
srid=00c01d04.0 erid=00c01d09.7 bitmap: (12):  00 f8 56 06 f8 56 07 c0 a1 01 c0 44
其数据块从1d04到1d09，也就是：

SQL> select sys.pkg_number_trans.f_hex_to_dec('1d04') as s_blk#,
  2  sys.pkg_number_trans.f_hex_to_dec('1d09') as e_blk#
  3  from dual;

S_BLK#     E_BLK#
---------- ----------
7428       7433

这个时候，
SQL> select substr(bitcol,1,1) as bitcol,dbms_rowid.rowid_block_number(rowid) as block# from t_bitmap_2;

BI     BLOCK#
-- ----------
B        7428
A        7428
A        7428
A        7429
B        7429
B        7429
B        7430
B        7430
B        7430
A        7431
A        7431
A        7431
B        7432
A        7432
A        7432
B        7433

这时，oracle放了很多的bit来对应这15条记录，但是oracle如何根据这些bit位来找对应的rowid就猜不出了。还希望各位牛人继续补充
本文转自


本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/Xviewee/archive/2008/09/25/2975345.aspx
  • 大小: 3.7 KB
  • 大小: 3.9 KB
  • 大小: 4.7 KB
  • 大小: 6.9 KB
  • 大小: 28.7 KB
分享到：
| Mysql源代码分析系列
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    bitmap索引的深入研究.doc

    bitmap索引的深入研究.doc

    Bitmap 性能和原理研究.docx

    Bitmap 性能和原理研究 Bitmap 是一种广泛应用于计算机科学和信息技术领域的数据结构，它可以高效地存储和查询大量的位图数据。在本文中，我们将深入探讨 Bitmap 的性能和原理，从最原始的 Bitmap 到 RoaringBitmap...

    简析Bitmap文件格式.rar_bitmap_blanket477

    在此，我们将深入探讨Bitmap文件格式的基本结构、特性以及在不同场景中的应用。 Bitmap图像由一个个像素点组成，每个像素都有自己的颜色信息。这种格式的文件通常包含以下几部分： 1. **文件头**：文件头包含了...

    关于Oracle数据库中的锁机制深入研究

    例如，如果死锁是由于特定类型的索引，如bitmap索引引起的，可能需要调整索引策略，如将bitmap索引改为normal索引，以减少死锁的风险。此外，优化事务设计和并发控制策略，比如减少事务的粒度，避免长时间持有锁，也...

    bitmap_in_sql.zip_位图 数据库

    位图索引是一种在数据库中存储和检索大数据量、低基数（low cardinality）列的高效方式。在SQL Server中，位图索引主要用于...通过研究“bitmap_in_sql.zip”中的内容，我们可以深入了解这一主题并应用到实际项目中。

    Oracle B＊树索引内部机制及其应用的研究.pdf

    1. 位图索引（Bitmap Index）：位图索引适合于具有大量重复值的列，它将每个唯一的键值映射为一个位图，通过位运算快速找到匹配的行。位图索引在数据仓库和只读场景下效果显著，但在频繁更新的环境中可能会增加...

    PostgresChina2018赖思超PostgreSQL10hash索引的WAL日志修改版final.pdf

    - Hash索引的数据结构包括元页（metapage）、桶页（bucket page）、溢出页（overflow page）和位图页（bitmap page）。 - 在创建Hash索引时，如果值非常长（例如很长的字符串）且只需要等值搜索时，使用Hash索引是...

    Open_BITmap.rar_open

    Open_BITMAP程序则是专门设计用来打开和处理这种8位图像的工具，对于研究图像处理或进行图形编程的开发者来说，这是一个非常实用的工具。 首先，我们要理解8位图像的基本概念。在8位图像中，每个像素由8个比特...

    ITPUB电子杂志

    关于shared pool的深入探讨 32bit oracle扩展SGA原理 32bit oracle中SGA_MAX_SIZE与单个进程PGA的制约关系 bitmap索引的一点探究 关于B*tree索引(index)的中度理解 本地管理表空间 倾力大奉献--...

    Algorithm-bitmap.zip

    位图库在计算机科学中是一种重要的数据结构，特别是在图像处理、图形用户界面设计以及算法实现等领域。...通过研究这个库，你可以深入理解位图数据结构和相关的算法，从而提升你在图形编程领域的技能。

    c#图像数据操作例子

    在C#编程环境中，图像处理是一项常见的任务，用于创建、编辑和分析图像。在这个特定的例子中，我们将关注如何使用C#进行图像...这个“testBitmap”项目可能就是一个实际应用这些概念的示例代码，值得深入研究和学习。

    The case for learned index structures-2018sigmod.pdf

    论文深入分析了在何种条件下学习型索引能超越传统索引结构，并讨论了设计这类索引结构的主要挑战。初步实验结果显示，通过神经网络，学习型索引可以在速度上比优化过的缓存B-Tree提高70%，同时在内存占用上减少了一...

    WPF使用Aforge实现USB摄像头拍照

    在本文中，我们将深入探讨如何使用Windows Presentation Foundation (WPF) 结合AForge.NET库来实现USB摄像头拍照的功能。AForge.NET是一个开源框架，提供了大量的计算机视觉和图像处理功能，非常适合于开发与图像...

    ClickHouse 高性能、可扩展和低成本的OLAP数据库 陈光剑 20230912

    ClickHouse是一款高性能、可扩展且低成本的在线分析处理(OLAP)数据库，由陈光剑等专家深入研究和实践。其设计哲学强调针对具体问题选择合适的算法，注重细节，全面衡量系统性能，接近实际生产环境，并通过持续的基准...

    数据库系统基础：高级篇(第5版)

    - Bitmap索引：适用于多列组合查询，尤其是当列值较少时。 - **索引优化**：如何选择合适的索引策略，以及如何维护索引的有效性。 #### 五、数据库查询优化 - **查询优化的目标**：减少查询执行时间和资源消耗。 -...

    行业-108 透彻研究通过explain命令得到的SQL执行计划（9）.rar

    - **Bitmap Index**：位图索引，适用于多列组合查询，节省存储空间，但在大量数据时可能带来额外的计算成本。 - **Hash Index**：适用于等值查询，但不支持范围查询和排序。 4. **连接操作** - **Nested Loop ...

    cstore

    此外，cstore可能还包含一些列式存储特有的索引结构，如B+树或Bitmap索引，以进一步优化查询效率。 在实际应用中，cstore可以与Hadoop、Spark等大数据处理框架集成，实现更复杂的数据分析任务。用户可以通过SQL接口...

    20181201Apache CarbonData & Spark Meetup

    1. **CarbonData核心特性**：包括列式存储、数据压缩、预排序索引（如Bloom Filter和Bitmap索引）、物化视图、以及对复杂数据类型的支持，这些特性使得CarbonData在大数据场景下表现优秀。 2. **Spark与CarbonData...

Magicbox
Global site tag (gtag.js) - Google Analytics