欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-11-12 19:55:10
本文内容 b-树(b-tree) 散列(hash) k-d 树(k-d tree) 点四叉树(point quadtree) 本文介绍关于 oracle 索引的结构。大...

本文内容 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-树算法确保树保持平衡,和叶节点在同一级上。

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

图 1 b-树

 

散列(hash)

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

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

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

图 2 散列

 

k-d 树(k-d tree)

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

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

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

图 3 2-d 树

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

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

点四叉树(point quadtree)

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

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

图 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 也行,用浏览器打开,会呈现下图:

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

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

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

下载 point qudatree python 演示