2024b树索引原理

B树索引、位图索引和散列索引知识点　　　　索引在数据结构上可以分为三种B树索引、位图索引和散列索引　　　　B树索引　　　　键值重复率低的字段比较适合使用B树索引。　　结构：
　　上图是B树索引的结构示意图，根节点和分支节点的结构类似，都包含指向下一层的指针及其键值范围，叶节点包含键值和行编号(RowID)。　　B树索引适合于选择性较低（即键值重复率较低）的列，当键值重复率较高时，使用B树索引有时可能还不如用全表扫描，因为需要在索引和原表之间不断切换，对表进行过多的单数据块访问，产生额外的I/O。　　
　　特点：　　　　1.索引不存储null值。　　　　更准确的说，单列索引不存储null值，复合索引不存储全为ｎｕｌｌ的值　　　　索引不能存储Null，所以对这列采用is null条件时，因为索引上根本没Null值，不能利用到索引，只　　　　能全表扫描。　　　　为什么索引列不能存Null值呢？将索引列值进行建树，其中必然涉及到诸多的比较操作。Null值　　　　的特殊性就在于参与的运算大多取值为null。这样的话，null值实际上是不能参与进建索引的　　　　过程。也就是说，null值不会像其他取值一样出现在索引树的叶子节点上。　　　　B树索引测试1：NULL是否存在索引上。　　　　　　create table btree_test(id number,code varchar2(10)); 　　create index idx_btree_test_id on btree_test(id,code); 　　select object_id from user_objects where object_name=’IDX_BTREE_TEST_ID’; 　　alter session set events ‘immediate trace name treedump level 59097’; 　　insert into btree_test values(null,null); 　　alter session set events ‘immediate trace name treedump level 59097′; 　　insert into btree_test values(null,’1’); 　　alter session set events ‘immediate trace name treedump level 59097’; 　　insert into btree_test values(1,null); 　　alter session set events ‘immediate trace name treedump level 59097′; 　　　　　　然后查看转储文件，admin数据库名ᆙ 　　　　发现这样的信息：　　　　* 2013-07-19 14:56:41.827 　　—– begin tree dump 　　leaf: 0xc (0: nrow: 0 rrow: 0) 　　—– end tree dump 　　* 2013-07-19 14:56:54.480 　　—– begin tree dump 　　leaf: 0xc (0: nrow: 1 rrow: 1) 　　—– end tree dump 　　* 2013-07-19 14:57:08.139 　　—– begin tree dump 　　leaf: 0xc (0: nrow: 2 rrow: 2) 　　—– end tree dump 　　　　nrow当前节点所含索引条目的数量（包括delete的条目）　　　　rrow有效的索引条目的数量　　　　可以发现：　　　　插入null,null时，有效的索引条目为0 　　插入null,1时，有效的索引条目为1 　　插入1,null时，有效的索引条目为2 　　　　所以，复合索引只有当要插入的值全为Null时才不能放入存入索引中。　　　　也可以这样看：　　　　 SELECT num_rows FROM user_indexes t WHERE t.index_name =’btree_test’; 　　　　　　2.不适合键值较少的列（重复数据较多的列）。　　　　假如索引列TYPE有5个键值，如果有1万条数据，那么 WHERE TYPE = 1将访问表中的2000个数据块。　　　　再加上访问索引块，一共要访问大于200个的数据块。　　　　如果全表扫描，假设10条数据一个数据块，那么只需访问1000个数据块，既然全表扫描访问的数据块　　　　少一些，肯定就不会利用索引了。　　　　3.前导模糊查询不能利用索引(like ‘%XX’或者like ‘%XX%’) 　　　　假如有这样一列code的值为’AAA’,’AAB’,’BAA’,’BAB’ ,如果where code like ‘%AB’条件，由于前面是　　　　模糊的，所以不能利用索引的顺序，必须一个个去找，看是否满足条件。这样会导致全索引扫描或者全表扫　　　　描。如果是这样的条件where code like ‘A % ‘，就可以查找CODE中A开头的CODE的位置，当碰到B开头的　　　　数据时，就可以停止查找了，因为后面的数据一定不满足要求。这样就可以利用索引了。　　　　　　位图索引　　和B树索引相反，位图索引适合键值重复率高的表，若重复值很低，则位图索引有可能非常大。由于位图索引采用0,1记录某行是否包含该键值，因此非常适合AND, OR, NOT，count等这样的逻辑操作。　　位图索引非常不适合有大量“写”的操作，因为每一个位图键值中，都可能对于多条记录，当修改一条记录更新位图键值时，会在对应的位图索引键上加锁，从而导致对其它记录的修改也会被阻塞。　　　　就是用位图表示的索引，对列的每个键值建立一个位图。　　　　如test表中有state这样一列，数据如下：　　　　 10 20 30 20 10 30 10 30 20 30 　　　　那么会建立三个位图，如下：　　　　BLOCK1 KEY=10 1 0 0 0 1 0 1 0 0 0 　　BLOCK2 KEY=20 1 0 0 0 1 0 1 0 0 0 　　BLOCK3 KEY=30 1 0 0 0 1 0 1 0 0 0 　　　　位图索引特点：　　　　　　1.相对于B*Tree索引,占用的空间非常小,创建和使用非常快。　　　　位图索引由于只存储键值的起止Rowid和位图,占用的空间非常少。　　　　　　2.不适合键值较多的列。　　　　3.不适合update、insert、delete频繁的列。　　　　4.可以存储null值。　　　　 B*Tree索引由于不记录空值,当基于is null的查询时,会使用全表扫描,而对位图索引列进　　　　行is null查询时,则可以使用索引。　　　　5.当select count(XX) 时,可以直接访问索引中一个位图就快速得出统计数据。　　　　6.当根据键值做and,or或 in(x,y,..)查询时,直接用索引的位图进行或运算,快速得出结果行数　　　　据。　　　　　　位图测试1：位图索引查询效率（省略）。　　　　位图测试2：修改数据时锁的范围。　　　　create table test_bitmap(id number,state number); 　　insert into test_bitmap values (1,10); 　　insert into test_bitmap values (2,10); 　　insert into test_bitmap values (3,20); 　　insert into test_bitmap values (4,20); 　　insert into test_bitmap values (5,10); 　　insert into test_bitmap values (6,30); 　　insert into test_bitmap values (7,30); 　　insert into test_bitmap values (8,20); 　　insert into test_bitmap values (9,30); 　　insert into test_bitmap values (10,20); 　　　　　　CREATE BITMAP INDEX INDEX_TESTBITMAP_STATE ON TEST_BITMAP(STATE); 　　　　开一个PLSQL窗口（SESSION1），执行　　update test_bitmap set state = 20 where id = 1; 　　　　另开一个PLSQL窗口（SESSION2），执行　　update test_bitmap set state = 20 where id = 2; 　　或者　　update test_bitmap set state = 10 where id = 4; 　　可以发现，状态为20的所有行被锁定。　　　　　　　　散列索引　　　　散列索引是根据HASH算法来构建的索引，所以检索速度很快，但不能范围查询。　　　　散列索引的特点　　　　　　1.只适合等值查询（包括= <> 和in），不适合模糊或范围查询　　

2024b树索引原理

相关推荐