索引在数据结构上可以分为三种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,..)查询时,直接用索引的位图进行或运算,快速得出结果行数
据。
散列索引
散列索引是根据HASH算法来构建的索引,所以检索速度很快,但不能范围查询。
散列索引的特点
1.只适合等值查询(包括= <> 和in),不适合模糊或范围查询
相关推荐
文件记录的组织方式 索引技术基础 B+树索引 散列索引 位图索引 多维空间索引 Grid file, R-tree, kd-tree, quadtree, Space Filling Curve
网格索引结构 (类散列结构) kd树 (类树结构) 四叉树 (类树结构) R树 (类树结构)
位图索引也是如此,仅仅只是是叶子节点不同B*数索引; 索引由根节点、分支节点和叶子节点组成。上级索引块包括下级索引块的索引数据,叶节点包括索引数据和确定行实际位置的rowid。 使用索引的目的: 加快查询速度 ...
位图索引 函数索引 视图 序列 利用OEM操作 第九章:备份与恢复 脱机备份与恢复 联机备份与恢复 逻辑备份与恢复 第十章:sqlplus基础 设置SQL*PLUS的运行环境 格式化查询命令 第十一章:分区表 概述 ...
关系数据库管理系统中常见索引: 顺序文件上的索引 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 消除重复 ...
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 只对部分...
第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 位图连接...
1. 层次结构模型: 层次结构模型实质上是一种有根结点的定向有序树,IMS(Information Manage-mentSystem)是其典型代表。 2. 网状结构模型:按照网状数据结构建立的数据库系统称为网状数据库系统,其典型代表是DBTG...
它可用于实现位图索引。 字对齐压缩的目标不是实现最佳压缩,而是提高查询处理时间。 因此,我们尝试节省 CPU 周期,可能以存储为代价。 然而,我们实施的 EWAH 方案在存储方面总是比未压缩的位阵列更有效。 实际...
它支持多种类型的数据结构,如字符串(strings)、散列(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)、位图(bitmaps)、超日志(hyperloglogs)、地理空间(geospatial)索引半径查询以及流...
Redis 提供数据结构,例如字符串、散列、列表、集合、带有范围查询的排序集、位图、超日志、地理空间索引和流。Redis 具有内置复制、 Lua 脚本编写、 LRU 垃圾清理、事务处理和不同级别的磁盘持久性,并通过 Redis ...
需要 索引结构 哈希,AVL树,T树,B树 B树,B+树,Hash 并发控制 ⼤粒度锁 细粒度锁加锁,解锁,死锁检测 查询优化 基于处理器代价以及 cache 代价 基于 I/O 代价 2、LRU: Least Recently Used,该算法的设计原则是...
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 ...
一种用于构建最小完美散列函数的高效外部存储器算法。 - 在 messagepack-rpc 上实现skipgraph。 - STL 地图用展开树实现。 - 可有效更新的双数组 trie 的 C++ 实现。 - 使用 O(1) 内存的快速且稳定的排序算法。 公共...
它支持字符串、散列、列表、集合、带范围查询的排序集合、位图、超loglogs、带半径查询和流的地理空间索引等数据结构。Redis具有内置的复制、Lua脚本、LRU退出、事务和不同级别的磁盘持久性,并通过Redis Sentinel和...
源代码和有关更新.......................................................................... 29 勘误表....................................................................................... 29 配置环境....
说明: 与 NLS_TIME_TZ_FORMAT 相似, 其中的一对值指定 TIMESTAMP 数据类型的默认值, 该类型除存储 YEAR, MONTH 和 DAY 日期值, HOUR, MINUTE 和 SECOND 时间值, 还存储 TIMEZONE_HOUR 和 TIMEZONE_MINUTE。...