Oracle 11g Release (11.1) 索引底层的数据结构

本文内容 B-树（B-tree） 散列（Hash） k-d 树（k-d tree） 点四叉树（Point Quadtree）

本文介绍关于 Oracle 索引的结构。大概了解 Oracle 索引底层的数据结构，从而更好地理解 Oracle 索引对增、删、改、查的性能。

B-树（B-tree）

非索引的结构能满足所有需要，但自平衡的 B-树索引结构更能优化在大数据集上检索的性能。每个 B-树节点拥有多个键和指针。特定 B-树支持的一个节点中键的最大数量是那颗树的顺序。每个节点都具有一个潜在的 order+1 指针，指向比它更低一级的节点。

例如，如图 1 所示，order=2 的 B-树具有三个指针，分别指向：比它第一个键小的子节点（最左边的指针）；比它第一个键大，比第二个键小的子节点（中间的指针）；比它第二个键大的子节点（最右边的指针）。因此，B-树算法，最大限度地减少定位记录所需的读写，通过传递比二叉树算法更少的节点，二叉树对每个确定的节点，用一个键和最多两个子节点（二叉树的结构是一个键值，左右两个指针，B-树是二叉树的扩展）。下图描述的是克努特变换（Knuth variation），它的索引由两部分组成：一个顺序集（Sequence set），提供快速顺序的访问数据；一个索引集（Index set），提供直接访问顺序集。

虽然，B-树的节点，一般不包含相同数量的数据值，并且他们通常包含一定量的未使用空间，B-树算法确保树保持平衡，和叶节点在同一级上。

图 1 B-树

散列（Hash）

散列根据一个给定字段值快速直接地访问一个特定的已存储的记录。每个记录被放置的位置是根据同一个函数，记录的一些字段域的函数计算的。并用相同的函数插入和更新。

散列的问题是记录的物理顺序与它们的逻辑顺序没有任何关系。另外，散列会在磁盘上存在大量未使用的区域。

图 2 散列

k-d 树（k-d tree）

具有两维的数据，例如经度和纬度，可用通过使用 k-d树变换，称为 2-d 树，被有效地存储和检索。

在这个结构，每个节点的数据类型，是字段信息，两个坐标，和指向两个子节点的左指针和右指针。

图 3 2-d 树

这种结构利于范围查询。也就是说，如果用户指定一个点(xx, xx)和一个距离，那么，查询会返回在这个指定的原来点距离内的所有点集合。

2-d 树很容易实现。但是因为，一个包含 k 个节点的 2-d 树具有 k 高度，因此，插入和查询复杂。

点四叉树（Point Quadtree）

点四叉树，在图 4 所示，也用来表示在一个两维空间中的点数据，但这些结构把区域划分为四个部分，而 2-d 树划分为两个。节点记录类型的字段由属性信息组成，包括两个坐标和指向四个子节点的方位点，按顺时针，如西北NW，西南SW，东北NE，东南SE。

图 4 Point Quadtree 索引结构

点四叉树跟 2-d 树一样也很容易实现。一个包含 k 个节点的四叉树具有 k 高度，插入和查询复杂。每个比较都要求在至少两个坐标上进行。然而，实际中，从 root 到 leaf 的长度在点四叉树中往往较短。

复制上面第二个链接里边提供的 Python 代码，做适当修改。因为，网页提供的代码只能运行在较低版本 Python。Python 3 之后的版本跟之前的差异较大。因此，下载本文最后源代码，并在 Python 3.3 的 IDLE 运行。会得到如下输出：

Python 3.3.0 (v3.3.0:bd8afb90ebf2, Sep 29 2012, 10:57:17) [MSC v.1600 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
 "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg xmlns="http://www.w3.org/2000/svg" version="1.1" width="400pt" height="400pt" viewBox="0 0 400 400">
 <g fill="none" stroke="blue">
 <line x1="1" y1="1" x2="1" y2="399" />
 <line x1="1" y1="399" x2="399" y2="399" />
 <line x1="399" y1="399" x2="399" y2="1" />
 <line x1="399" y1="1" x2="1" y2="1" />
 <line x1="200" y1="1" x2="200" y2="399" />
 <line x1="1" y1="200" x2="399" y2="200" />
 <line x1="100" y1="1" x2="100" y2="200" />
 <line x1="1" y1="100" x2="200" y2="100" />
 <line x1="50" y1="1" x2="50" y2="100" />
……

复制输出的结果，命名为 .svg，.html 也行，用浏览器打开，会呈现下图：

图 5 一个 8*8 大小的点四叉树区域

看这个图，从左上角开始，顺时针。你可以当做“根据需要，是否要点，不断按 4 个分裂其中一个方块”。

下载 Point Qudatree Python 演示

赞 (0)

相关推荐

  • oracle逻辑结构分析

    oracle的逻辑结构包括表空间(tablespace),段(segment),区(extent),数据块(data block) oracle数据库在逻辑上是由多个表间组成的,表空间中存储的对象叫段,比如数据段,索引段,和回退段.段由区组成,区是磁盘分配的最小单位.段的增大是通过增加区的个数来实现的.每个区的大小是数据块大小的整数倍,区的大小可以不相同:数据块是数据库中最小的I/O单位,同时也是内存数据缓冲区的单位,及数据文件存储空间单位.块的大小由参数DB_BLOCK_SIZE设置,其值应设

  • Oracle中scott表结构与简单查询实例分析

    本文实例讲述了Oracle中scott表结构与简单查询的方法.分享给大家供大家参考.具体分析如下: 1.scott用户的表的结构 查看表结构 desc 表名;//desc emp; emp表: SQL> desc emp; 名称 是否为空? 类型 ----------------- -------- ------------ EMPNO NOT NULL NUMBER(4) 雇员编号 ENAME VARCHAR2(10) 雇员姓名 JOB VARCHAR2(9) 雇员职位 MGR NUMBER(

  • oracle复制表结构和复制表数据语句分享

    1. 复制表结构及其数据: 复制代码 代码如下: create table table_name_new as select * from table_name_old 2. 只复制表结构: 复制代码 代码如下: create table table_name_new as select * from table_name_old where 1=2; 或者: 复制代码 代码如下: create table table_name_new like table_name_old 3. 只复制表数据

  • Oracle SQL树形结构查询

    oracle中的select语句可以用START WITH...CONNECT BY PRIOR子句实现递归查询,connect by 是结构化查询中用到的,其基本语法是: 复制代码 代码如下: select * from tablename start with cond1 connect by cond2 where cond3; 简单说来是将一个树状结构存储在一张表里,比如一个表中存在两个字段: id,parentid那么通过表示每一条记录的parent是谁,就可以形成一个树状结构. 用上

  • BS结构中使用PHP访问ORACLE LOB

    PHP,即"PHP: Hypertext Preprocessor",是一种广泛用于 Open Source(开放源代码)并可以嵌入 HTML 的多用途脚本语言.它的语法接近 C.Java 和 Perl,易于学习.该语言的主要目标是让 Web 开发人员快速的书写动态生成的网页,然而,PHP 的功能并不局限于此.PHP普遍被认为可以更快和更有效地实现复杂的编程任务,而且正是因为它的更稳定以及占用更少资源的优点成为开发B/S结构系统的必备的WEB脚本设计语言,扮演着类似中间件的角色,即语法

  • oracle 数据库学习 基本结构介绍

    oracle 数据库学习 基本结构介绍

    普及一下oracle的基础知识,总结一下,oracle 是由实例和数据库组成.结构如下: oracle数据库由实例.数据库组成: * 数据库由数据文件(包含oracle 数据.索引.表结构等数据).控制文件(包括每个表的操作信息).日志文件(数据操作sql语句).参数文件.口令文件.日志归档文件(归档模式下)(服务器崩溃.硬盘损坏情况下,通过日志恢复时用) * 实例由 内存结构(memory strutct) 和 后台进程(background processor)组成. 内存结构组成: * P

  • Oracle 11g Release (11.1) 索引底层的数据结构

    Oracle 11g Release (11.1) 索引底层的数据结构

    本文内容 B-树(B-tree) 散列(Hash) k-d 树(k-d tree) 点四叉树(Point Quadtree) 本文介绍关于 Oracle 索引的结构.大概了解 Oracle 索引底层的数据结构,从而更好地理解 Oracle 索引对增.删.改.查的性能. B-树(B-tree) 非索引的结构能满足所有需要,但自平衡的 B-树索引结构更能优化在大数据集上检索的性能.每个 B-树节点拥有多个键和指针.特定 B-树支持的一个节点中键的最大数量是那颗树的顺序.每个节点都具有一个潜在的 or

  • ORACLE 11g从 11.2.0.1升级到11.2.0.4 详细实战教程

    ORACLE 11g从 11.2.0.1升级到11.2.0.4 详细实战教程

     1.准备安装 查看当前oracle版本,确定是比较旧的11.2.0.1 [oracle@hch_test_121_90 ~]$ rlwrap sqlplus / as sysdba SQL*Plus: Release 11.2.0.1.0 Production on Fri Mar 17 15:20:45 2017 Copyright (c) 1982, 2009, Oracle. All rights reserved. Connected to: Oracle Database 11g E

  • java基于JDBC连接Oracle 11g Release2实例分析

    本文实例讲述了java基于JDBC连接Oracle 11g Release2的方法.分享给大家供大家参考.具体如下: Oracle 11g Release 2 的 JDBC 连接似乎有所不同 ,如果你收到下面的异常: Listener refused the connection with the following error:ORA-12505, TNS:listener does not currently know of SID given in connect descriptor.

  • ORACLE检查找出损坏索引(Corrupt Indexes)的方法详解

    ORACLE检查找出损坏索引(Corrupt Indexes)的方法详解

    索引 索引与表一样,也属于段(segment)的一种.里面存放了用户的数据,跟表一样需要占用磁盘空间.索引是一种允许直接访问数据表中某一数据行的树型结构,为了提高查询效率而引入,是一个独立于表的对象,可以存放在与表不同的表空间中.索引记录中存有索引关键字和指向表中数据的指针(地址).对索引进行的I/O操作比对表进行操作要少很多.索引一旦被建立就将被Oracle系统自动维护,查询语句中不用指定使用哪个索引. 从物理上说,索引通常可以分为:分区和非分区索引.常规B树索引.位图(bitmap)索引.翻

  • Oracle 11g如何清理数据库的历史日志详解

    本文主要给大家介绍了关于Oracle 11g清理数据库历史日志的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍 1. 创建存放数据库待删除日志文件路径 用于存放准备删除,这里假设放在/home/Oracle/delete路径下 $ cd /home/oracle/delete $ mkdir -p audit_file_dest background_dump_dest user_dump_dest core_dump_dest listenr_log_dest 2. 查

  • Oracle 11g控制文件全部丢失从零开始重建控制文件

    介绍 控制文件(control file)是一个相当小的文件(最多能增长到64M左右),其中包含Oracle需要的其他文件的一个目录.参数文件告知实例控制文件的位置,控制文件则告知示例数据库和在线重做日志文件的位置.控制文件还告知了Oracle其他一些事情,如已发生检查点的有关信息.数据库名(必须和db_name参数匹配).创建数据库的时间戳.归档重做日志的历史(有时这会让控制文件变大).RMAN信息等. 控制文件应该通过硬件(RAID)多路保存,如果不支持镜像,则要通过Oracle多路保存.应

  • Oracle 11g收集多列统计信息详解

    前言 通常,当我们将SQL语句提交给Oracle数据库时,Oracle会选择一种最优方式来执行,这是通过查询优化器Query Optimizer来实现的.CBO(Cost-Based Optimizer)是Oracle默认使用的查询优化器模式.在CBO中,SQL执行计划的生成,是以一种寻找成本(Cost)最优为目标导向的执行计划探索过程.所谓成本(Cost)就是将CPU和IO消耗整合起来的量化指标,每一个执行计划的成本就是经过优化器内部公式估算出的数字值. 我们在写SQL语句的时候,经常会碰到w

  • oracle 11g配置 解决启动连接数据库出现的ora错误

    oracle 11g配置 解决启动连接数据库出现的ora错误

    按照网上方法并结合实践,整理了一下(以后忘记了可以看看),oracle登录问题的解决办法: 常见的登录连接oracle数据库时遇到的问题ora-12560,01034,27101,00119,00132等,可以按照以下步骤检查和解决. Oracle11g数据库监听,数据库启动  1.添加监听程序(服务器端) 打开net manager 添加监听 添加监听位置(网络地址) 添加数据库服务(oracle主目录可以不填) 2.添加服务命名  3.测试 利用服务器端sqlplus工具E:\app\204

  • Oracle 11g下编译使用BBED的方法教程

    BBED介绍: BBED(Oracle Block Browerand EDitor Tool),用来直接查看和修改数据文件数据的一个工具,是Oracle一款内部工具,可以直接修改Oracle数据文件块的内容,在一些极端恢复场景下比较有用.该工具不受Oracle支持,所以默认是没有生成可执行文件的,在使用前需要重新连接. 本文详细介绍了关于Oracle 11g下编译使用BBED的方法教程,下面话不多说,来一起看看详细的介绍: 环境:RHEL 6.4 + Oracle 11.2.0.4 1. 拷贝

  • ORA-28002 Oracle 11g存在密码过期问题解决方案

    故障现象 Oracle Database 11g 数据库普通用户登录时提示 ORA-28002: the password will expire within 7 days [11:01:00oracle@dvd db_1]$sqlplus wang/oracle SQL*Plus: Release 11.2.0.1.0 Production on Fri Nov 16 11:01:23 2012 Copyright (c) 1982, 2009, Oracle. All rights res

随机推荐