本文內(nèi)容 B-樹（B-tree） 散列（Hash） k-d 樹（k-d tree） 點(diǎn)四叉樹（Point Quadtree）

本文介紹關(guān)于 Oracle 索引的結(jié)構(gòu)。大概了解 Oracle 索引底層的數(shù)據(jù)結(jié)構(gòu)，從而更好地理解 Oracle 索引對(duì)增、刪、改、查的性能。

非索引的結(jié)構(gòu)能滿足所有需要，但自平衡的 B-樹索引結(jié)構(gòu)更能優(yōu)化在大數(shù)據(jù)集上檢索的性能。每個(gè) B-樹節(jié)點(diǎn)擁有多個(gè)鍵和指針。特定 B-樹支持的一個(gè)節(jié)點(diǎn)中鍵的最大數(shù)量是那顆樹的順序。每個(gè)節(jié)點(diǎn)都具有一個(gè)潛在的 order+1 指針，指向比它更低一級(jí)的節(jié)點(diǎn)。

例如，如圖 1 所示，order=2 的 B-樹具有三個(gè)指針，分別指向：比它第一個(gè)鍵小的子節(jié)點(diǎn)（最左邊的指針）；比它第一個(gè)鍵大，比第二個(gè)鍵小的子節(jié)點(diǎn)（中間的指針）；比它第二個(gè)鍵大的子節(jié)點(diǎn)（最右邊的指針）。因此，B-樹算法，最大限度地減少定位記錄所需的讀寫，通過傳遞比二叉樹算法更少的節(jié)點(diǎn)，二叉樹對(duì)每個(gè)確定的節(jié)點(diǎn)，用一個(gè)鍵和最多兩個(gè)子節(jié)點(diǎn)（二叉樹的結(jié)構(gòu)是一個(gè)鍵值，左右兩個(gè)指針，B-樹是二叉樹的擴(kuò)展）。下圖描述的是克努特變換（Knuth variation），它的索引由兩部分組成：一個(gè)順序集（Sequence set），提供快速順序的訪問數(shù)據(jù)；一個(gè)索引集（Index set），提供直接訪問順序集。

雖然，B-樹的節(jié)點(diǎn)，一般不包含相同數(shù)量的數(shù)據(jù)值，并且他們通常包含一定量的未使用空間，B-樹算法確保樹保持平衡，和葉節(jié)點(diǎn)在同一級(jí)上。

圖 1 B-樹

散列根據(jù)一個(gè)給定字段值快速直接地訪問一個(gè)特定的已存儲(chǔ)的記錄。每個(gè)記錄被放置的位置是根據(jù)同一個(gè)函數(shù)，記錄的一些字段域的函數(shù)計(jì)算的。并用相同的函數(shù)插入和更新。

散列的問題是記錄的物理順序與它們的邏輯順序沒有任何關(guān)系。另外，散列會(huì)在磁盤上存在大量未使用的區(qū)域。

圖 2 散列

具有兩維的數(shù)據(jù)，例如經(jīng)度和緯度，可用通過使用 k-d樹變換，稱為 2-d 樹，被有效地存儲(chǔ)和檢索。

在這個(gè)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型，是字段信息，兩個(gè)坐標(biāo)，和指向兩個(gè)子節(jié)點(diǎn)的左指針和右指針。

圖 3 2-d 樹

這種結(jié)構(gòu)利于范圍查詢。也就是說，如果用戶指定一個(gè)點(diǎn)(xx, xx)和一個(gè)距離，那么，查詢會(huì)返回在這個(gè)指定的原來點(diǎn)距離內(nèi)的所有點(diǎn)集合。

2-d 樹很容易實(shí)現(xiàn)。但是因?yàn)?，一個(gè)包含 k 個(gè)節(jié)點(diǎn)的 2-d 樹具有 k 高度，因此，插入和查詢復(fù)雜。

點(diǎn)四叉樹，在圖 4 所示，也用來表示在一個(gè)兩維空間中的點(diǎn)數(shù)據(jù)，但這些結(jié)構(gòu)把區(qū)域劃分為四個(gè)部分，而 2-d 樹劃分為兩個(gè)。節(jié)點(diǎn)記錄類型的字段由屬性信息組成，包括兩個(gè)坐標(biāo)和指向四個(gè)子節(jié)點(diǎn)的方位點(diǎn)，按順時(shí)針，如西北NW，西南SW，東北NE，東南SE。

圖 4 Point Quadtree 索引結(jié)構(gòu)

點(diǎn)四叉樹跟 2-d 樹一樣也很容易實(shí)現(xiàn)。一個(gè)包含 k 個(gè)節(jié)點(diǎn)的四叉樹具有 k 高度，插入和查詢復(fù)雜。每個(gè)比較都要求在至少兩個(gè)坐標(biāo)上進(jìn)行。然而，實(shí)際中，從 root 到 leaf 的長(zhǎng)度在點(diǎn)四叉樹中往往較短。

復(fù)制上面第二個(gè)鏈接里邊提供的 Python 代碼，做適當(dāng)修改。因?yàn)?，網(wǎng)頁(yè)提供的代碼只能運(yùn)行在較低版本 Python。Python 3 之后的版本跟之前的差異較大。因此，下載本文最后源代碼，并在 Python 3.3 的 IDLE 運(yùn)行。會(huì)得到如下輸出：

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" />

……