本文内容 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-树算法确保树保持平衡，和叶节点在同一级上。 [url=http://images.cnblogs.com/cnblogs_com/liuning8023/201210/201210172125104135.gif][img]http://files.jb51.net/file_images/article/201211/2012111516285225.gif[/img] [/url] [b]图 1 B-树[/b]   散列（Hash） 散列根据一个给定字段值快速直接地访问一个特定的已存储的记录。每个记录被放置的位置是根据同一个函数，记录的一些字段域的函数计算的。并用相同的函数插入和更新。 散列的问题是记录的物理顺序与它们的逻辑顺序没有任何关系。另外，散列会在磁盘上存在大量未使用的区域。 [url=http://images.cnblogs.com/cnblogs_com/liuning8023/201210/201210172125104069.gif][img]http://files.jb51.net/file_images/article/201211/2012111516285226.gif[/img] [/url] [b]图 2 散列[/b]   k-d 树（k-d tree） 具有两维的数据，例如经度和纬度，可用通过使用 k-d树变换，称为 2-d 树，被有效地存储和检索。 在这个结构，每个节点的数据类型，是字段信息，两个坐标，和指向两个子节点的左指针和右指针。 [url=http://images.cnblogs.com/cnblogs_com/liuning8023/201210/201210172126467487.gif][img]http://files.jb51.net/file_images/article/201211/2012111516285227.gif[/img] [/url] [b]图 3 2-d 树[/b] 这种结构利于范围查询。也就是说，如果用户指定一个点(xx, xx)和一个距离，那么，查询会返回在这个指定的原来点距离内的所有点集合。 2-d 树很容易实现。但是因为，一个包含 k 个节点的 2-d 树具有 k 高度，因此，插入和查询复杂。 点四叉树（Point Quadtree）

---

点四叉树，在图 4 所示，也用来表示在一个两维空间中的点数据，但这些结构把区域划分为四个部分，而 2-d 树划分为两个。节点记录类型的字段由属性信息组成，包括两个坐标和指向四个子节点的方位点，按顺时针，如西北NW，西南SW，东北NE，东南SE。 [url=http://images.cnblogs.com/cnblogs_com/liuning8023/201210/201210172126503711.gif][img]http://files.jb51.net/file_images/article/201211/2012111516285228.gif[/img] [/url] [b]图 4 Point Quadtree 索引结构[/b] 点四叉树跟 2-d 树一样也很容易实现。一个包含 k 个节点的四叉树具有 k 高度，插入和查询复杂。每个比较都要求在至少两个坐标上进行。然而，实际中，从 root 到 leaf 的长度在点四叉树中往往较短。 [quote] [url=http://zh.wikipedia.org/zh/File:Point_quadtree.svg][/url] 复制上面第二个链接里边提供的 Python 代码，做适当修改。因为，网页提供的代码只能运行在较低版本 Python。Python 3 之后的版本跟之前的差异较大。因此，下载本文最后源代码，并在 Python 3.3 的 IDLE 运行。会得到如下输出： [/quote]