`

B树索引、位图索引和散列索引

 
阅读更多

索引在数据结构上可以分为三种B树索引、位图索引和散列索引

 

B树索引

 

结构:




 

 
 

 

 

特点:

 

1.索引不存储null值。

 

   更准确的说,单列索引不存储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\数据库名\udump

 

发现这样的信息:

 

*** 2013-07-19 14:56:41.827

----- begin tree dump

leaf: 0x140142c 20976684 (0: nrow: 0 rrow: 0)

----- end tree dump

*** 2013-07-19 14:56:54.480

----- begin tree dump

leaf: 0x140142c 20976684 (0: nrow: 1 rrow: 1)

----- end tree dump

*** 2013-07-19 14:57:08.139

----- begin tree dump

leaf: 0x140142c 20976684 (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开头的

 

数据时,就可以停止查找了,因为后面的数据一定不满足要求。这样就可以利用索引了。

 

 

位图索引

 

 

    就是用位图表示的索引,对列的每个键值建立一个位图。

 

    如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),不适合模糊或范围查询

 

分享到:
评论

相关推荐

    数据库索引技术ppt

    文件记录的组织方式 索引技术基础 B+树索引 散列索引 位图索引 多维空间索引 Grid file, R-tree, kd-tree, quadtree, Space Filling Curve

    多维索引PPT

    网格索引结构 (类散列结构) kd树 (类树结构) 四叉树 (类树结构) R树 (类树结构)

    oracle使用索引与不使用索引的性能详析

    位图索引也是如此,仅仅只是是叶子节点不同B*数索引; 索引由根节点、分支节点和叶子节点组成。上级索引块包括下级索引块的索引数据,叶节点包括索引数据和确定行实际位置的rowid。 使用索引的目的: 加快查询速度 ...

    ORACLE教材

    位图索引 函数索引 视图 序列 利用OEM操作 第九章:备份与恢复 脱机备份与恢复 联机备份与恢复 逻辑备份与恢复 第十章:sqlplus基础 设置SQL*PLUS的运行环境 格式化查询命令 第十一章:分区表 概述 ...

    数据库系统概论chp3-2.pptx

    关系数据库管理系统中常见索引: 顺序文件上的索引 B+树索引 散列(hash)索引 位图索引 特点: B+树索引具有动态平衡的优点 HASH索引具有查找速度快的特点 数据库系统概论chp3-2全文共66页,当前为第6页。...

    数据库系统实现

    5.4.4 位图索引的管理 习题 5.5 小结 5.6 参考文献 第6章 查询执行 6.1 一种查询代数 6.1.1 并、交和差 6.1.2 选择操作符 6.1.3 投影操作符 6.1.4 关系的积 6.1.5 连接 6.1.6 消除重复 ...

    Oracle 9i&10g编程艺术:深入数据库体系结构(全本)含脚本

    11.3.1 什么情况下应该使用位图索引? 449 11.3.2 位图联结索引 453 11.3.3 位图索引小结 455 11.4 基于函数的索引 456 11.4.1 重要的实现细节 456 11.4.2 一个简单的基于函数的索引例子 457 11.4.3 只对部分...

    (E文)基于成本的Oracle优化法则.pdf

    第8章 位图索引 169 8.1 入门 170 8.1.1 索引组件 174 8.1.2 表组件 175 8.2 位图合并 177 8.2.1 较低的基数 179 8.2.2 空值列 182 8.3 CPU成本计算 185 8.4 一些有趣的示例 186 8.4.1 多列索引 187 8.4.2 位图连接...

    oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串

    1. 层次结构模型: 层次结构模型实质上是一种有根结点的定向有序树,IMS(Information Manage-mentSystem)是其典型代表。 2. 网状结构模型:按照网状数据结构建立的数据库系统称为网状数据库系统,其典型代表是DBTG...

    javabitset源码-csharpewah:C#中的压缩位图

    它可用于实现位图索引。 字对齐压缩的目标不是实现最佳压缩,而是提高查询处理时间。 因此,我们尝试节省 CPU 周期,可能以存储为代价。 然而,我们实施的 EWAH 方案在存储方面总是比未压缩的位阵列更有效。 实际...

    Redis-x64-3.2.100的安装版java可用

    它支持多种类型的数据结构,如字符串(strings)、散列(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)、位图(bitmaps)、超日志(hyperloglogs)、地理空间(geospatial)索引半径查询以及流...

    redis window最新免安装版本

    Redis 提供数据结构,例如字符串、散列、列表、集合、带有范围查询的排序集、位图、超日志、地理空间索引和流。Redis 具有内置复制、 Lua 脚本编写、 LRU 垃圾清理、事务处理和不同级别的磁盘持久性,并通过 Redis ...

    数据库系统概念:存储和文件结构.pdf

    需要 索引结构 哈希,AVL树,T树,B树 B树,B+树,Hash 并发控制 ⼤粒度锁 细粒度锁加锁,解锁,死锁检测 查询优化 基于处理器代价以及 cache 代价 基于 I/O 代价 2、LRU: Least Recently Used,该算法的设计原则是...

    Oracle SQL高级编程(资深Oracle专家力作,OakTable团队推荐)--随书源代码

    12.2.2 位图索引 340 12.2.3 索引组织表 341 12.3 分区索引 343 12.3.1 局部索引 343 12.3.2 全局索引 345 12.3.3 散列分区与范围分区 346 12.4 与应用特点相匹配的解决方案 348 12.4.1 压缩索引 348 ...

    java笔试题算法-big-data-made-easy:大数据变得容易

    一种用于构建最小完美散列函数的高效外部存储器算法。 - 在 messagepack-rpc 上实现skipgraph。 - STL 地图用展开树实现。 - 可有效更新的双数组 trie 的 C++ 实现。 - 使用 O(1) 内存的快速且稳定的排序算法。 公共...

    win版redis客户端安装包,可视化工具

    它支持字符串、散列、列表、集合、带范围查询的排序集合、位图、超loglogs、带半径查询和流的地理空间索引等数据结构。Redis具有内置的复制、Lua脚本、LRU退出、事务和不同级别的磁盘持久性,并通过Redis Sentinel和...

    Oracle编程艺术

    源代码和有关更新.......................................................................... 29 勘误表....................................................................................... 29 配置环境....

    Oracle9i的init.ora参数中文说明

    说明: 与 NLS_TIME_TZ_FORMAT 相似, 其中的一对值指定 TIMESTAMP 数据类型的默认值, 该类型除存储 YEAR, MONTH 和 DAY 日期值, HOUR, MINUTE 和 SECOND 时间值, 还存储 TIMEZONE_HOUR 和 TIMEZONE_MINUTE。...

Global site tag (gtag.js) - Google Analytics