5-空間存儲(chǔ)和索引解析

1、第五章第五章 空間存儲(chǔ)和索引空間存儲(chǔ)和索引l問(wèn)題的提出問(wèn)題的提出l物理存儲(chǔ)介質(zhì)物理存儲(chǔ)介質(zhì)l緩沖區(qū)管理緩沖區(qū)管理l存儲(chǔ)組織存儲(chǔ)組織l存取路徑：索引結(jié)構(gòu)存取路徑：索引結(jié)構(gòu)問(wèn)題的提出問(wèn)題的提出l索引的意義索引的意義n空間索引，也稱(chēng)為空間訪問(wèn)方法（空間索引，也稱(chēng)為空間訪問(wèn)方法（Spatial access method-SAM）就是指依據(jù)空間對(duì)象的位置和形狀或者空間對(duì)象之間的某就是指依據(jù)空間對(duì)象的位置和形狀或者空間對(duì)象之間的某種空間關(guān)系按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)。種空間關(guān)系按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)。包含空間對(duì)象的概要信息，如對(duì)象的標(biāo)識(shí)、外包絡(luò)矩形、包含空間對(duì)象的概要信息，如對(duì)象的標(biāo)識(shí)、外包

2、絡(luò)矩形、及指向空間對(duì)象實(shí)體的指針。及指向空間對(duì)象實(shí)體的指針。n空間數(shù)據(jù)庫(kù)索引技術(shù)是對(duì)存儲(chǔ)在介質(zhì)上的數(shù)據(jù)位置空間數(shù)據(jù)庫(kù)索引技術(shù)是對(duì)存儲(chǔ)在介質(zhì)上的數(shù)據(jù)位置信息的描述，是為了快速訪問(wèn)一條特定查詢所請(qǐng)求信息的描述，是為了快速訪問(wèn)一條特定查詢所請(qǐng)求的數(shù)據(jù)，而無(wú)需遍歷整個(gè)數(shù)據(jù)庫(kù)。的數(shù)據(jù)，而無(wú)需遍歷整個(gè)數(shù)據(jù)庫(kù)。問(wèn)題的提出問(wèn)題的提出n空間索引的提出基于兩個(gè)因素空間索引的提出基于兩個(gè)因素計(jì)算機(jī)的體系結(jié)構(gòu)將存儲(chǔ)器分為內(nèi)存和外存計(jì)算機(jī)的體系結(jié)構(gòu)將存儲(chǔ)器分為內(nèi)存和外存訪問(wèn)兩種存儲(chǔ)器一次所花費(fèi)的時(shí)間相差訪問(wèn)兩種存儲(chǔ)器一次所花費(fèi)的時(shí)間相差10萬(wàn)倍以上萬(wàn)倍以上外存儲(chǔ)器作為存儲(chǔ)數(shù)據(jù)的主要設(shè)備，訪問(wèn)所花費(fèi)的代價(jià)，要求對(duì)外存儲(chǔ)器

3、作為存儲(chǔ)數(shù)據(jù)的主要設(shè)備，訪問(wèn)所花費(fèi)的代價(jià)，要求對(duì)數(shù)據(jù)存儲(chǔ)的位置和結(jié)構(gòu)必須加以組織和索引。數(shù)據(jù)存儲(chǔ)的位置和結(jié)構(gòu)必須加以組織和索引。傳統(tǒng)索引技術(shù)對(duì)空間數(shù)據(jù)庫(kù)的不適應(yīng)性傳統(tǒng)索引技術(shù)對(duì)空間數(shù)據(jù)庫(kù)的不適應(yīng)性傳統(tǒng)索引技術(shù)只是基于一維數(shù)據(jù)之間的關(guān)系判讀（大于、等于和傳統(tǒng)索引技術(shù)只是基于一維數(shù)據(jù)之間的關(guān)系判讀（大于、等于和小于），而空間數(shù)據(jù)的多維性很難判斷小于），而空間數(shù)據(jù)的多維性很難判斷存儲(chǔ)器分級(jí)管理存儲(chǔ)器分級(jí)管理n空間索引技術(shù)的研究思路空間索引技術(shù)的研究思路目標(biāo)映射思路目標(biāo)映射思路基于傳統(tǒng)數(shù)據(jù)庫(kù)的索引機(jī)制：傳統(tǒng)數(shù)據(jù)庫(kù)的多屬性可以看成多維基于傳統(tǒng)數(shù)據(jù)庫(kù)的索引機(jī)制：傳統(tǒng)數(shù)據(jù)庫(kù)的多屬性可以看成多維空間上的點(diǎn)，因

4、此多屬性數(shù)據(jù)索引（空間上的點(diǎn)，因此多屬性數(shù)據(jù)索引（KD-樹(shù)、網(wǎng)格文件）可以直接樹(shù)、網(wǎng)格文件）可以直接用于索引空間中的點(diǎn)狀地物。用于索引空間中的點(diǎn)狀地物。問(wèn)題的提出問(wèn)題的提出曲線、多邊形、多面體，則可以將其先映射成更高緯空間的點(diǎn)，曲線、多邊形、多面體，則可以將其先映射成更高緯空間的點(diǎn)，再采用點(diǎn)狀目標(biāo)索引技術(shù)。再采用點(diǎn)狀目標(biāo)索引技術(shù)。目標(biāo)復(fù)制思路目標(biāo)復(fù)制思路復(fù)雜的空間幾何體映射高維空間點(diǎn)后，幾何體的空間關(guān)系發(fā)生了復(fù)雜的空間幾何體映射高維空間點(diǎn)后，幾何體的空間關(guān)系發(fā)生了變化，查找效率低。變化，查找效率低。于是提出了不允許索引子重疊的索引法。這種方法，將索引空間于是提出了不允許索引子重疊的索引法。這種

5、方法，將索引空間劃分成許多索引子空間，索引目標(biāo)屬于與其相交的子空間。劃分成許多索引子空間，索引目標(biāo)屬于與其相交的子空間。缺點(diǎn)：導(dǎo)致目標(biāo)重復(fù)存儲(chǔ)，增加了缺點(diǎn)：導(dǎo)致目標(biāo)重復(fù)存儲(chǔ)，增加了Insert/Delete等操作的復(fù)雜度。等操作的復(fù)雜度。目標(biāo)界定思路目標(biāo)界定思路如果允許索引子重疊，則可以將空間幾何體界定在某一索引子空如果允許索引子重疊，則可以將空間幾何體界定在某一索引子空間內(nèi)，則目標(biāo)的重復(fù)存儲(chǔ)可以避免。間內(nèi)，則目標(biāo)的重復(fù)存儲(chǔ)可以避免。索引子空間的重疊，必然導(dǎo)致多條查找路徑，因此這種研究的思索引子空間的重疊，必然導(dǎo)致多條查找路徑，因此這種研究的思路重點(diǎn)是索引子空間重疊最小化。路重點(diǎn)是索引子空間重

6、疊最小化?；敬鎯?chǔ)聯(lián)機(jī)存儲(chǔ)物理存儲(chǔ)介質(zhì)層次寄存器高速緩沖存儲(chǔ)器主存儲(chǔ)器快閃存儲(chǔ)器磁盤(pán)存儲(chǔ)器脫機(jī)存儲(chǔ)光盤(pán)存儲(chǔ)器磁帶存儲(chǔ)器容量速度快快慢慢小小大大物理存儲(chǔ)介質(zhì)：基本存儲(chǔ)l寄存器（寄存器（register）nCPU的一部分，用于暫存運(yùn)算中間結(jié)果的一部分，用于暫存運(yùn)算中間結(jié)果n與運(yùn)算部件直接連接，速度最快，極少（幾十個(gè)）與運(yùn)算部件直接連接，速度最快，極少（幾十個(gè)）l高速緩沖存儲(chǔ)器（高速緩沖存儲(chǔ)器（cache memory）nCPU的一部分，用于緩存主存儲(chǔ)器，解決主存儲(chǔ)器的一部分，用于緩存主存儲(chǔ)器，解決主存儲(chǔ)器跟不上跟不上CPU讀寫(xiě)速度要求的矛盾。讀寫(xiě)速度要求的矛盾。n在在CPU中，速度極快，容量?。◣?/p>

7、十中，速度極快，容量小（幾十K2M）n操作系統(tǒng)底層管理操作系統(tǒng)底層管理物理存儲(chǔ)介質(zhì)：基本存儲(chǔ)l主存儲(chǔ)器（主存儲(chǔ)器（main memory）-內(nèi)存內(nèi)存n通過(guò)總線與通過(guò)總線與CPU相連，存儲(chǔ)運(yùn)算所需的數(shù)據(jù)和指令相連，存儲(chǔ)運(yùn)算所需的數(shù)據(jù)和指令n速度很快（納秒級(jí)），一般容量在幾十速度很快（納秒級(jí)），一般容量在幾十M幾個(gè)幾個(gè)Gn隨機(jī)訪問(wèn)：訪問(wèn)任何存儲(chǔ)單元，時(shí)間相同。隨機(jī)訪問(wèn)：訪問(wèn)任何存儲(chǔ)單元，時(shí)間相同。n易失性：斷電丟失。易失性：斷電丟失。n操作系統(tǒng)提供機(jī)制，應(yīng)用程序管理。操作系統(tǒng)提供機(jī)制，應(yīng)用程序管理。物理存儲(chǔ)介質(zhì)：在線存儲(chǔ)l快閃存儲(chǔ)器（快閃存儲(chǔ)器（flash memory）n通過(guò)外設(shè)接口與總線相連，

8、存儲(chǔ)永久保留的數(shù)據(jù)通過(guò)外設(shè)接口與總線相連，存儲(chǔ)永久保留的數(shù)據(jù)n速度受到存儲(chǔ)介質(zhì)和接口限制速度受到存儲(chǔ)介質(zhì)和接口限制n隨機(jī)訪問(wèn)，非易失性，斷電不丟失隨機(jī)訪問(wèn)，非易失性，斷電不丟失n文件系統(tǒng)管理，可以通過(guò)操作系統(tǒng)在線訪問(wèn)文件系統(tǒng)管理，可以通過(guò)操作系統(tǒng)在線訪問(wèn)l磁盤(pán)存儲(chǔ)器（磁盤(pán)存儲(chǔ)器（disk memory）n同上，但是機(jī)械裝置，速度更慢同上，但是機(jī)械裝置，速度更慢物理存儲(chǔ)介質(zhì)：脫機(jī)存儲(chǔ)l光盤(pán)存儲(chǔ)器（光盤(pán)存儲(chǔ)器（CDROM/CDR/CDRW/DVD）n脫機(jī)存儲(chǔ)，保存?zhèn)浞莼蛘邭v史檔案脫機(jī)存儲(chǔ)，保存?zhèn)浞莼蛘邭v史檔案n分為光物理盤(pán)，光化學(xué)盤(pán)和光磁盤(pán)分為光物理盤(pán)，光化學(xué)盤(pán)和光磁盤(pán)n只讀，可寫(xiě)一次，可重復(fù)讀寫(xiě)

9、只讀，可寫(xiě)一次，可重復(fù)讀寫(xiě)n機(jī)械裝置，隨機(jī)訪問(wèn)，速度更低機(jī)械裝置，隨機(jī)訪問(wèn)，速度更低n有標(biāo)準(zhǔn)數(shù)據(jù)記錄格式，操作系統(tǒng)提供文件系統(tǒng)接口有標(biāo)準(zhǔn)數(shù)據(jù)記錄格式，操作系統(tǒng)提供文件系統(tǒng)接口訪問(wèn)訪問(wèn)物理存儲(chǔ)介質(zhì)：脫機(jī)存儲(chǔ)l磁帶存儲(chǔ)器（磁帶存儲(chǔ)器（tape）n脫機(jī)存儲(chǔ)，保存?zhèn)浞莼蛘邭v史檔案脫機(jī)存儲(chǔ)，保存?zhèn)浞莼蛘邭v史檔案n電磁記錄原理電磁記錄原理n機(jī)械裝置，順序訪問(wèn)機(jī)械裝置，順序訪問(wèn)n速度最低，容量?jī)r(jià)格比最高（至幾百速度最低，容量?jī)r(jià)格比最高（至幾百G）磁盤(pán)存儲(chǔ)器l主要內(nèi)容主要內(nèi)容n磁盤(pán)物理特性磁盤(pán)物理特性n磁盤(pán)性能度量磁盤(pán)性能度量n磁盤(pán)塊存取的優(yōu)化磁盤(pán)塊存取的優(yōu)化n磁盤(pán)陣列技術(shù)磁盤(pán)陣列技術(shù)RAID磁盤(pán)存儲(chǔ)物理特性

10、l 盤(pán)片盤(pán)片n單片或多片單片或多片n同心圓磁道同心圓磁道track，磁道密度決定容量磁道密度決定容量n扇區(qū)扇區(qū)sector、扇區(qū)號(hào)、扇區(qū)號(hào)n柱面柱面cylinder-各盤(pán)各盤(pán)片相同磁道組成片相同磁道組成l 磁頭磁頭n固定磁頭固定磁頭n活動(dòng)磁頭活動(dòng)磁頭l 驅(qū)動(dòng)臂驅(qū)動(dòng)臂磁盤(pán)存儲(chǔ)器性能度量l 容量：磁盤(pán)所能容納的字節(jié)數(shù)容量：磁盤(pán)所能容納的字節(jié)數(shù)l 存取時(shí)間：從發(fā)出讀寫(xiě)請(qǐng)求到數(shù)據(jù)開(kāi)始傳輸之間的時(shí)間存取時(shí)間：從發(fā)出讀寫(xiě)請(qǐng)求到數(shù)據(jù)開(kāi)始傳輸之間的時(shí)間n尋道（址）時(shí)間：移動(dòng)磁盤(pán)臂，定位到正確磁道所需的時(shí)間。尋道（址）時(shí)間：移動(dòng)磁盤(pán)臂，定位到正確磁道所需的時(shí)間。（平均（平均4 10毫秒）毫秒）n旋轉(zhuǎn)等待時(shí)間：等

11、待被存取的扇區(qū)出現(xiàn)在讀寫(xiě)頭下所需的時(shí)旋轉(zhuǎn)等待時(shí)間：等待被存取的扇區(qū)出現(xiàn)在讀寫(xiě)頭下所需的時(shí)間。間。 （平均（平均25毫秒）毫秒）l 數(shù)據(jù)傳輸率：從磁盤(pán)獲得數(shù)據(jù)或者向磁盤(pán)存儲(chǔ)數(shù)據(jù)的速數(shù)據(jù)傳輸率：從磁盤(pán)獲得數(shù)據(jù)或者向磁盤(pán)存儲(chǔ)數(shù)據(jù)的速率率l 平均故障時(shí)間（可靠性）：預(yù)期系統(tǒng)無(wú)故障連續(xù)運(yùn)行的平均故障時(shí)間（可靠性）：預(yù)期系統(tǒng)無(wú)故障連續(xù)運(yùn)行的平均時(shí)間平均時(shí)間MTBF磁盤(pán)塊存取的優(yōu)化l在主存儲(chǔ)器中對(duì)塊進(jìn)行緩沖以減少塊的讀寫(xiě)次數(shù)在主存儲(chǔ)器中對(duì)塊進(jìn)行緩沖以減少塊的讀寫(xiě)次數(shù)l按柱面組織數(shù)據(jù)按柱面組織數(shù)據(jù)-相關(guān)信息存放同一柱面和相鄰相關(guān)信息存放同一柱面和相鄰柱面。柱面。l磁盤(pán)臂調(diào)度磁盤(pán)臂調(diào)度 - 電梯算法電梯算法 l

12、利用非易失性利用非易失性RAM作為寫(xiě)緩沖作為寫(xiě)緩沖l預(yù)讀和讀寫(xiě)雙緩沖預(yù)讀和讀寫(xiě)雙緩沖緩沖區(qū)管理緩沖區(qū)管理l緩沖區(qū)緩沖區(qū)buffern主存儲(chǔ)器中用于存儲(chǔ)磁盤(pán)塊的拷貝的部分，由固定主存儲(chǔ)器中用于存儲(chǔ)磁盤(pán)塊的拷貝的部分，由固定數(shù)目的緩沖塊構(gòu)成數(shù)目的緩沖塊構(gòu)成 l緩沖區(qū)管理器緩沖區(qū)管理器nDBMS的一個(gè)軟件模塊的一個(gè)軟件模塊n負(fù)責(zé)緩沖區(qū)空間分配調(diào)度的子系統(tǒng)負(fù)責(zé)緩沖區(qū)空間分配調(diào)度的子系統(tǒng)l緩沖區(qū)管理的目的緩沖區(qū)管理的目的n減少磁盤(pán)和主存儲(chǔ)器之間傳輸?shù)膲K的數(shù)目減少磁盤(pán)和主存儲(chǔ)器之間傳輸?shù)膲K的數(shù)目緩沖區(qū)管理基本流程BufferManagerDiskRead/WriteRequestsBuffer緩沖區(qū)替換策

13、略寫(xiě)回磁盤(pán)策略緩沖區(qū)替換策略緩沖區(qū)替換策略l 最近使用（最近使用（LRU）n替換出最長(zhǎng)時(shí)間沒(méi)有讀或?qū)戇^(guò)的塊替換出最長(zhǎng)時(shí)間沒(méi)有讀或?qū)戇^(guò)的塊l 先進(jìn)先出（先進(jìn)先出（FIFO）n替換出被同一個(gè)塊占用時(shí)間最長(zhǎng)的緩沖塊替換出被同一個(gè)塊占用時(shí)間最長(zhǎng)的緩沖塊l “時(shí)鐘時(shí)鐘”算法算法nLRU的一個(gè)常見(jiàn)的、有效的近似的一個(gè)常見(jiàn)的、有效的近似l 系統(tǒng)控制系統(tǒng)控制n查詢優(yōu)化器或者其它的查詢優(yōu)化器或者其它的DBMS部件可以給緩沖區(qū)管理器提供部件可以給緩沖區(qū)管理器提供建議來(lái)避免象建議來(lái)避免象LRU，F(xiàn)IFO，或者時(shí)鐘這樣的嚴(yán)格的策略可能，或者時(shí)鐘這樣的嚴(yán)格的策略可能引起的問(wèn)題引起的問(wèn)題最近使用-Least Recent

14、ly Usedl基本方法基本方法n緩沖區(qū)管理器保持一個(gè)表，登記每個(gè)緩沖塊緩沖區(qū)管理器保持一個(gè)表，登記每個(gè)緩沖塊被訪問(wèn)被訪問(wèn)的最后一次時(shí)間的最后一次時(shí)間n每個(gè)數(shù)據(jù)庫(kù)訪問(wèn)在這個(gè)表中生成一個(gè)表項(xiàng)。每個(gè)數(shù)據(jù)庫(kù)訪問(wèn)在這個(gè)表中生成一個(gè)表項(xiàng)。lLRU是一個(gè)有效的策略是一個(gè)有效的策略n直覺(jué)上，長(zhǎng)時(shí)間沒(méi)有使用的緩沖區(qū)比那些最近訪問(wèn)直覺(jué)上，長(zhǎng)時(shí)間沒(méi)有使用的緩沖區(qū)比那些最近訪問(wèn)過(guò)的緩沖區(qū)有更小的再訪問(wèn)的可能性過(guò)的緩沖區(qū)有更小的再訪問(wèn)的可能性n但也有例外但也有例外先進(jìn)先出FIFO- First-In First-Outl 基本方法基本方法n緩沖區(qū)管理器保持一個(gè)表，登記當(dāng)前占用緩沖區(qū)的各個(gè)塊裝緩沖區(qū)管理器保持一個(gè)表，登

15、記當(dāng)前占用緩沖區(qū)的各個(gè)塊裝入緩沖區(qū)的時(shí)間入緩沖區(qū)的時(shí)間n當(dāng)塊從磁盤(pán)讀入內(nèi)存的時(shí)候，生成一個(gè)表項(xiàng)當(dāng)塊從磁盤(pán)讀入內(nèi)存的時(shí)候，生成一個(gè)表項(xiàng)n當(dāng)塊被訪問(wèn)時(shí)，不需要修改這個(gè)表當(dāng)塊被訪問(wèn)時(shí)，不需要修改這個(gè)表l 與與LRU相比，相比，F(xiàn)IFO需要較少的維護(hù)需要較少的維護(hù)n但它存在更多的問(wèn)題但它存在更多的問(wèn)題n例如被重復(fù)使用的，例如被重復(fù)使用的，B-樹(shù)索引的根塊將最終變成一個(gè)緩沖區(qū)樹(shù)索引的根塊將最終變成一個(gè)緩沖區(qū)中最舊的塊，它將被寫(xiě)回到磁盤(pán)上，很快又被重新讀入另一中最舊的塊，它將被寫(xiě)回到磁盤(pán)上，很快又被重新讀入另一個(gè)緩沖區(qū)。個(gè)緩沖區(qū)。 “時(shí)鐘時(shí)鐘”算法算法l基本方法基本方法n將緩沖區(qū)看作一個(gè)環(huán)。一將緩沖區(qū)看作

16、一個(gè)環(huán)。一個(gè)指針指向一個(gè)緩沖塊個(gè)指針指向一個(gè)緩沖塊n每一個(gè)緩沖塊有一個(gè)每一個(gè)緩沖塊有一個(gè)“標(biāo)標(biāo)志志”，0或或1n帶有帶有0標(biāo)志的是很可能被替標(biāo)志的是很可能被替換出去的緩沖塊換出去的緩沖塊n剛讀入和訪問(wèn)過(guò)的塊標(biāo)記剛讀入和訪問(wèn)過(guò)的塊標(biāo)記為為1n指針旋轉(zhuǎn)過(guò)程中，不斷將指針旋轉(zhuǎn)過(guò)程中，不斷將1變?yōu)樽優(yōu)?01101100緩沖區(qū)管理系統(tǒng)控制l查詢優(yōu)化器或者其它的查詢優(yōu)化器或者其它的DBMS部件可以給緩沖區(qū)部件可以給緩沖區(qū)管理器提供建議管理器提供建議n例如，將某些塊定義為例如，將某些塊定義為“固定的固定的”來(lái)強(qiáng)迫它們保持來(lái)強(qiáng)迫它們保持在內(nèi)存中，如在內(nèi)存中，如B-樹(shù)的根、數(shù)據(jù)字典中的塊。樹(shù)的根、數(shù)據(jù)字典中的塊

17、。n又如，對(duì)于象一遍散列連接那樣的算法，查詢處理又如，對(duì)于象一遍散列連接那樣的算法，查詢處理器可以器可以“固定固定”較小的關(guān)系的塊，使得確保在全部較小的關(guān)系的塊，使得確保在全部時(shí)間內(nèi)它都將留在內(nèi)存中。時(shí)間內(nèi)它都將留在內(nèi)存中。 塊寫(xiě)回控制策略l被釘住的塊被釘住的塊n為了使數(shù)據(jù)庫(kù)系統(tǒng)能夠從崩潰中恢復(fù)，必須限制一為了使數(shù)據(jù)庫(kù)系統(tǒng)能夠從崩潰中恢復(fù)，必須限制一個(gè)塊寫(xiě)回磁盤(pán)的時(shí)間。不允許寫(xiě)回磁盤(pán)的塊稱(chēng)為被個(gè)塊寫(xiě)回磁盤(pán)的時(shí)間。不允許寫(xiě)回磁盤(pán)的塊稱(chēng)為被釘住的塊釘住的塊l塊的強(qiáng)制寫(xiě)出塊的強(qiáng)制寫(xiě)出n某些情況下，盡管不需要一個(gè)塊所占用的緩沖區(qū)空某些情況下，盡管不需要一個(gè)塊所占用的緩沖區(qū)空間，仍必須把這個(gè)塊寫(xiě)回磁盤(pán)。

18、這樣的寫(xiě)操作稱(chēng)為間，仍必須把這個(gè)塊寫(xiě)回磁盤(pán)。這樣的寫(xiě)操作稱(chēng)為塊的強(qiáng)制寫(xiě)出。塊的強(qiáng)制寫(xiě)出。數(shù)據(jù)存儲(chǔ)組織l數(shù)據(jù)庫(kù)中的數(shù)據(jù)存儲(chǔ)在操作系統(tǒng)管理的文件中數(shù)據(jù)庫(kù)中的數(shù)據(jù)存儲(chǔ)在操作系統(tǒng)管理的文件中n域域-記錄記錄-(塊塊)-文件文件l域根據(jù)類(lèi)型占據(jù)不同大小空間域根據(jù)類(lèi)型占據(jù)不同大小空間n定長(zhǎng)域類(lèi)型定長(zhǎng)域類(lèi)型(Char)n變長(zhǎng)域類(lèi)型變長(zhǎng)域類(lèi)型(Varchar)n二進(jìn)制大對(duì)象類(lèi)型（二進(jìn)制大對(duì)象類(lèi)型（BLOB） 常用于空間復(fù)雜對(duì)象的存儲(chǔ)，至少可以提供存儲(chǔ)常用于空間復(fù)雜對(duì)象的存儲(chǔ)，至少可以提供存儲(chǔ)管理和事物支持管理和事物支持?jǐn)?shù)據(jù)存儲(chǔ)組織l 記錄由域順序排列組成記錄由域順序排列組成n定長(zhǎng)記錄定長(zhǎng)記錄n變長(zhǎng)記錄：含有變

19、長(zhǎng)域的記錄變長(zhǎng)記錄：含有變長(zhǎng)域的記錄l 定長(zhǎng)記錄文件定長(zhǎng)記錄文件 文件中所有的記錄都具有相同的長(zhǎng)度，從而一個(gè)塊中所有文件中所有的記錄都具有相同的長(zhǎng)度，從而一個(gè)塊中所有的記錄都是等長(zhǎng)的的記錄都是等長(zhǎng)的l 變長(zhǎng)記錄文件變長(zhǎng)記錄文件 文件中的記錄可以有不同的長(zhǎng)度，從而一個(gè)塊中的各個(gè)記文件中的記錄可以有不同的長(zhǎng)度，從而一個(gè)塊中的各個(gè)記錄可以具有不同的長(zhǎng)度錄可以具有不同的長(zhǎng)度數(shù)據(jù)存儲(chǔ)組織l 定長(zhǎng)記錄文件的順定長(zhǎng)記錄文件的順序存儲(chǔ)序存儲(chǔ)n塊的大小應(yīng)為記錄大塊的大小應(yīng)為記錄大小的整倍數(shù)小的整倍數(shù)對(duì)齊對(duì)齊n刪除記錄代價(jià)高刪除記錄代價(jià)高刪除標(biāo)記，或有效指針刪除標(biāo)記，或有效指針鏈接鏈接 記錄記錄0Perryrid

20、geA-102400 記錄記錄1Rouond HillA-305350 記錄記錄2MianusA-215700 記錄記錄3DowntownA-101500 記錄記錄4RedwoodA-222700 記錄記錄5PerryridgeA-201900 記錄記錄6BrightonA-217750 記錄記錄7DowntownA-110600 記錄記錄8PerryridgeA-218700數(shù)據(jù)存儲(chǔ)組織l 變長(zhǎng)記錄文件變長(zhǎng)記錄文件n多種記錄類(lèi)型在一個(gè)文件中存儲(chǔ)多種記錄類(lèi)型在一個(gè)文件中存儲(chǔ) n記錄類(lèi)型允許一個(gè)或多個(gè)字段是變長(zhǎng)的記錄類(lèi)型允許一個(gè)或多個(gè)字段是變長(zhǎng)的 n記錄類(lèi)型允許可重復(fù)的字段記錄類(lèi)型允許可重復(fù)的字

21、段l 變長(zhǎng)記錄文件的變長(zhǎng)記錄文件的定長(zhǎng)表示法定長(zhǎng)表示法n預(yù)留空間：使用長(zhǎng)度為最大記錄長(zhǎng)度的定長(zhǎng)記錄。對(duì)較短記預(yù)留空間：使用長(zhǎng)度為最大記錄長(zhǎng)度的定長(zhǎng)記錄。對(duì)較短記錄未使用的空間用特殊的空值或記錄終結(jié)符號(hào)來(lái)填充。錄未使用的空間用特殊的空值或記錄終結(jié)符號(hào)來(lái)填充。 n使用指針：變長(zhǎng)記錄用一系列通過(guò)指針鏈接起來(lái)的定長(zhǎng)記錄使用指針：變長(zhǎng)記錄用一系列通過(guò)指針鏈接起來(lái)的定長(zhǎng)記錄來(lái)表示。來(lái)表示。 變長(zhǎng)記錄文件：預(yù)留空間法記錄記錄0PerryridgeA-102400A-201900A-218700記錄記錄1Round HillA-305350 記錄記錄2MianusA-215700 記錄記錄3DowntownA

22、-101500A-110600 記錄記錄4RedwoodA-222700 記錄記錄5BrightonA-217750 變長(zhǎng)記錄文件：使用指針 記錄記錄0PerryridgeA-102400 記錄記錄1Rouond HillA-305350 記錄記錄2MianusA-215700 記錄記錄3DowntownA-101500 記錄記錄4RedwoodA-222700 記錄記錄5A-201900 記錄記錄6BrightonA-217750 記錄記錄7A-110600 記錄記錄8A-218700變長(zhǎng)記錄文件：錨塊和溢出塊錨塊錨塊PerryridgeA-102400Round HillA-305350M

23、ianusA-215700DowntownA-101500RedwoodA-222700BrightonA-217750A-210900A-218700A-110600溢出塊溢出塊變長(zhǎng)記錄文件：字節(jié)流表示法l字節(jié)流表示：把每個(gè)記錄作為一個(gè)連續(xù)的字節(jié)流字節(jié)流表示：把每個(gè)記錄作為一個(gè)連續(xù)的字節(jié)流存儲(chǔ)，每個(gè)記錄的末尾附加一個(gè)特殊的記錄終止存儲(chǔ)，每個(gè)記錄的末尾附加一個(gè)特殊的記錄終止符號(hào)符號(hào)0PerryridgeA-102400A-201900A-2187001Round HillA-3053502MianusA-2157003DowntownA-101500A-1106004RedwoodA-2227

24、005BrightonA-217750變長(zhǎng)記錄文件：分槽的頁(yè)結(jié)構(gòu)l分槽的頁(yè)結(jié)構(gòu)：每個(gè)塊的開(kāi)始處有一個(gè)分槽的頁(yè)結(jié)構(gòu)：每個(gè)塊的開(kāi)始處有一個(gè)塊頭塊頭記錄條目個(gè)數(shù)空閑空間塊頭大小位置空閑空間尾指針數(shù)據(jù)存儲(chǔ)組織l文件中記錄的組織文件中記錄的組織n關(guān)系中的各個(gè)記錄存放在文件中的什么位置關(guān)系中的各個(gè)記錄存放在文件中的什么位置n堆文件組織：記錄沒(méi)有順序堆文件組織：記錄沒(méi)有順序,一條記錄可以放在文件一條記錄可以放在文件中的任何地方。中的任何地方。 n散列文件組織：散列函數(shù)的計(jì)算結(jié)果確定記錄應(yīng)存散列文件組織：散列函數(shù)的計(jì)算結(jié)果確定記錄應(yīng)存儲(chǔ)到文件的哪個(gè)塊中。儲(chǔ)到文件的哪個(gè)塊中。 n順序文件組織：記錄根據(jù)搜索碼的值

25、順序存儲(chǔ)順序文件組織：記錄根據(jù)搜索碼的值順序存儲(chǔ)數(shù)據(jù)字典的存儲(chǔ)l數(shù)據(jù)字典：數(shù)據(jù)庫(kù)的描述信息數(shù)據(jù)字典：數(shù)據(jù)庫(kù)的描述信息n關(guān)系模式信息：邏輯結(jié)構(gòu)關(guān)系模式信息：邏輯結(jié)構(gòu)n關(guān)系存儲(chǔ)信息：物理結(jié)構(gòu)關(guān)系存儲(chǔ)信息：物理結(jié)構(gòu)n用戶信息：安全控制用戶信息：安全控制n統(tǒng)計(jì)信息：數(shù)量統(tǒng)計(jì)信息：數(shù)量/容量統(tǒng)計(jì)容量統(tǒng)計(jì)n索引信息索引信息 RDBMS中，數(shù)據(jù)字典和普通關(guān)系同樣存儲(chǔ)中，數(shù)據(jù)字典和普通關(guān)系同樣存儲(chǔ)索索 引引l索引：支持對(duì)于所要求的數(shù)據(jù)進(jìn)行快速定位的附索引：支持對(duì)于所要求的數(shù)據(jù)進(jìn)行快速定位的附加的數(shù)據(jù)結(jié)構(gòu)。加的數(shù)據(jù)結(jié)構(gòu)。n每個(gè)索引結(jié)構(gòu)有一個(gè)特定的搜索碼與之關(guān)聯(lián)。每個(gè)索引結(jié)構(gòu)有一個(gè)特定的搜索碼與之關(guān)聯(lián)。索引按一定

26、的方式存儲(chǔ)搜索碼的值，并將搜索碼與包含該索引按一定的方式存儲(chǔ)搜索碼的值，并將搜索碼與包含該搜索碼的記錄關(guān)聯(lián)起來(lái)。搜索碼的記錄關(guān)聯(lián)起來(lái)。 n搜索碼：用于在文件中查找記錄的搜索碼：用于在文件中查找記錄的屬性或?qū)傩约瘜傩曰驅(qū)傩约?學(xué)號(hào)學(xué)號(hào)記錄起始地址記錄起始地址基本索引結(jié)構(gòu)l順序索引順序索引 索引基于對(duì)搜索碼值的一種排序索引基于對(duì)搜索碼值的一種排序l散列索引散列索引 索引基于將搜索碼值平均分布到若干散列桶（索引基于將搜索碼值平均分布到若干散列桶（hash buckets）中）中l(wèi)內(nèi)外存索引優(yōu)化策略不同內(nèi)外存索引優(yōu)化策略不同n內(nèi)存索引偏向減少存儲(chǔ)空間需求，對(duì)速度不敏感內(nèi)存索引偏向減少存儲(chǔ)空間需求，對(duì)

27、速度不敏感n外存索引偏向減少訪問(wèn)次數(shù)，對(duì)速度敏感外存索引偏向減少訪問(wèn)次數(shù)，對(duì)速度敏感基本索引結(jié)構(gòu)：順序索引l順序索引中按照一定的順序存儲(chǔ)搜索碼的值順序索引中按照一定的順序存儲(chǔ)搜索碼的值n主索引：若文件中的記錄按照某個(gè)搜索碼值的順序主索引：若文件中的記錄按照某個(gè)搜索碼值的順序來(lái)存儲(chǔ)，則這個(gè)搜索碼所對(duì)應(yīng)的索引稱(chēng)作主索引，來(lái)存儲(chǔ)，則這個(gè)搜索碼所對(duì)應(yīng)的索引稱(chēng)作主索引，或者或者聚類(lèi)（聚集、聚簇）索引聚類(lèi)（聚集、聚簇）索引（cluster index）n輔助索引：索引對(duì)應(yīng)的搜索碼值的順序與文件記錄輔助索引：索引對(duì)應(yīng)的搜索碼值的順序與文件記錄的存儲(chǔ)順序不一致，也稱(chēng)作的存儲(chǔ)順序不一致，也稱(chēng)作非聚集索引非聚集索

28、引基本索引結(jié)構(gòu)：散列索引l在外存中按照桶散列，通過(guò)散列函數(shù)將搜索碼值在外存中按照桶散列，通過(guò)散列函數(shù)將搜索碼值對(duì)應(yīng)到桶地址對(duì)應(yīng)到桶地址n桶（桶（bucket）是能存儲(chǔ)一條或多條記錄的一個(gè)存儲(chǔ)單）是能存儲(chǔ)一條或多條記錄的一個(gè)存儲(chǔ)單位，每個(gè)桶包括一個(gè)或多個(gè)磁盤(pán)塊位，每個(gè)桶包括一個(gè)或多個(gè)磁盤(pán)塊n散列犧牲存儲(chǔ)效率散列犧牲存儲(chǔ)效率 可以通過(guò)可擴(kuò)充散列，在數(shù)據(jù)庫(kù)大小變化時(shí)對(duì)桶可以通過(guò)可擴(kuò)充散列，在數(shù)據(jù)庫(kù)大小變化時(shí)對(duì)桶進(jìn)行分裂或合并，保持一定的空間效率進(jìn)行分裂或合并，保持一定的空間效率對(duì)索引技術(shù)評(píng)價(jià)的考慮對(duì)索引技術(shù)評(píng)價(jià)的考慮l訪問(wèn)類(lèi)型訪問(wèn)類(lèi)型n能有效支持?jǐn)?shù)據(jù)庫(kù)訪問(wèn)的類(lèi)型；能有效支持?jǐn)?shù)據(jù)庫(kù)訪問(wèn)的類(lèi)型；l訪問(wèn)時(shí)

29、間訪問(wèn)時(shí)間n訪問(wèn)一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)所需的時(shí)間；訪問(wèn)一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)所需的時(shí)間； l插入時(shí)間插入時(shí)間n在索引中插入一個(gè)新數(shù)據(jù)項(xiàng)所需的時(shí)間；在索引中插入一個(gè)新數(shù)據(jù)項(xiàng)所需的時(shí)間；l刪除時(shí)間刪除時(shí)間n從索引中刪除一個(gè)數(shù)據(jù)項(xiàng)所需的時(shí)間；從索引中刪除一個(gè)數(shù)據(jù)項(xiàng)所需的時(shí)間；l空間開(kāi)銷(xiāo)空間開(kāi)銷(xiāo)n索引結(jié)構(gòu)所需的額外的存儲(chǔ)空間。索引結(jié)構(gòu)所需的額外的存儲(chǔ)空間。 聚類(lèi)聚類(lèi)/聚集（聚集（cluster）l以某種搜索碼值的順序安排記錄的物理存儲(chǔ)以某種搜索碼值的順序安排記錄的物理存儲(chǔ)n搜索碼值相近的記錄在存儲(chǔ)上也相近，表現(xiàn)在磁道搜索碼值相近的記錄在存儲(chǔ)上也相近，表現(xiàn)在磁道和扇區(qū)上的相鄰和扇區(qū)上的相鄰n降低對(duì)于常見(jiàn)的大查詢的響

30、應(yīng)時(shí)間降低對(duì)于常見(jiàn)的大查詢的響應(yīng)時(shí)間單搜索碼值的查找，范圍值的查找單搜索碼值的查找，范圍值的查找降低尋道時(shí)間和尋扇區(qū)時(shí)間降低尋道時(shí)間和尋扇區(qū)時(shí)間提高磁盤(pán)緩存的命中率提高磁盤(pán)緩存的命中率聚類(lèi)聚類(lèi)/聚集（聚集（cluster）l簡(jiǎn)單數(shù)據(jù)類(lèi)型的聚類(lèi)簡(jiǎn)單數(shù)據(jù)類(lèi)型的聚類(lèi)n整數(shù)、定點(diǎn)數(shù)（整數(shù)、定點(diǎn)數(shù)（Numeric(6,2)）、浮點(diǎn)數(shù)）、浮點(diǎn)數(shù)(Float)、字、字符串、日期符串、日期n具有完整的一維全序性質(zhì)，其值可以排成線性單調(diào)具有完整的一維全序性質(zhì)，其值可以排成線性單調(diào)序列，和存儲(chǔ)器的線性性質(zhì)相符序列，和存儲(chǔ)器的線性性質(zhì)相符l復(fù)雜數(shù)據(jù)類(lèi)型的聚類(lèi)復(fù)雜數(shù)據(jù)類(lèi)型的聚類(lèi)n兩維以上的簡(jiǎn)單數(shù)據(jù)類(lèi)型的組合向量?jī)删S以

31、上的簡(jiǎn)單數(shù)據(jù)類(lèi)型的組合向量n如空間數(shù)據(jù)、多搜索碼的結(jié)構(gòu)如空間數(shù)據(jù)、多搜索碼的結(jié)構(gòu)聚類(lèi)聚類(lèi)/聚集（聚集（cluster）l多維數(shù)據(jù)類(lèi)型的聚類(lèi)方法多維數(shù)據(jù)類(lèi)型的聚類(lèi)方法n將高維地址空間映射到一維地址空間將高維地址空間映射到一維地址空間一一對(duì)應(yīng)的映射，保證沒(méi)有地址遺漏和重復(fù)一一對(duì)應(yīng)的映射，保證沒(méi)有地址遺漏和重復(fù)保持距離的映射，保證高維中相鄰的地址也在一維中相鄰保持距離的映射，保證高維中相鄰的地址也在一維中相鄰n一一對(duì)應(yīng)的映射容易構(gòu)造一一對(duì)應(yīng)的映射容易構(gòu)造n保持距離只能近似的實(shí)現(xiàn)保持距離只能近似的實(shí)現(xiàn)Z序映射和序映射和Hilbert曲線映射曲線映射二維空間聚類(lèi)二維空間聚類(lèi)l考慮有限二維整數(shù)平面考慮有限

32、二維整數(shù)平面n以每次四分網(wǎng)格的形式遞歸劃分平面以每次四分網(wǎng)格的形式遞歸劃分平面n遞歸劃分的層次決定坐標(biāo)的二進(jìn)制位數(shù)遞歸劃分的層次決定坐標(biāo)的二進(jìn)制位數(shù)n每個(gè)網(wǎng)格具有唯一的二維坐標(biāo)作為地址每個(gè)網(wǎng)格具有唯一的二維坐標(biāo)作為地址0000011011011011yx兩次遞歸劃分的網(wǎng)格，可以多次遞歸劃分網(wǎng)格Z序映射Z序映射編碼l讀入讀入x和和y坐標(biāo)的二進(jìn)制表示；坐標(biāo)的二進(jìn)制表示；l隔行掃描二進(jìn)制位到一個(gè)字符串；隔行掃描二進(jìn)制位到一個(gè)字符串；l計(jì)算出結(jié)果二進(jìn)制串的十進(jìn)制值。計(jì)算出結(jié)果二進(jìn)制串的十進(jìn)制值。Z序映射編碼例子Hilbert曲線映射Hilbert曲線映射編碼l 讀入讀入x和和y坐標(biāo)的二進(jìn)制表示；坐標(biāo)的

33、二進(jìn)制表示；l 隔行掃描二進(jìn)制位到一個(gè)字符串；隔行掃描二進(jìn)制位到一個(gè)字符串；l 將字符串從左到右分成若干將字符串從左到右分成若干2位長(zhǎng)的串位長(zhǎng)的串si(i=1.n)，并將，并將其換成其換成規(guī)定的規(guī)定的十進(jìn)制數(shù)，如：十進(jìn)制數(shù)，如：n000, 011, 103, 112l 對(duì)十進(jìn)制數(shù)進(jìn)行替換對(duì)十進(jìn)制數(shù)進(jìn)行替換n對(duì)與數(shù)組中第對(duì)與數(shù)組中第1位數(shù)字位數(shù)字j：若若j =0，則第，則第2位數(shù)字位數(shù)字13, 31若若j =3，則第，則第2位數(shù)字位數(shù)字02, 20l 自左至右，自上至下的順序連接所有串，計(jì)算十進(jìn)制值，自左至右，自上至下的順序連接所有串，計(jì)算十進(jìn)制值，得到一維的地址得到一維的地址Hilbert曲線

34、映射編碼例子聚類(lèi)的磁盤(pán)訪問(wèn)性能l基本假定基本假定n有限范圍的多維空間，有限個(gè)網(wǎng)格單元有限范圍的多維空間，有限個(gè)網(wǎng)格單元n映射將多維空間的單元指定一個(gè)整數(shù)地址映射將多維空間的單元指定一個(gè)整數(shù)地址n每個(gè)網(wǎng)格單元對(duì)應(yīng)一個(gè)磁盤(pán)頁(yè)面的存儲(chǔ)每個(gè)網(wǎng)格單元對(duì)應(yīng)一個(gè)磁盤(pán)頁(yè)面的存儲(chǔ)n連續(xù)地址的單元存儲(chǔ)在相鄰磁盤(pán)頁(yè)面連續(xù)地址的單元存儲(chǔ)在相鄰磁盤(pán)頁(yè)面l性能衡量指標(biāo)性能衡量指標(biāo)n對(duì)一片連續(xù)空間范圍網(wǎng)格的訪問(wèn)涉及盡量少間斷的對(duì)一片連續(xù)空間范圍網(wǎng)格的訪問(wèn)涉及盡量少間斷的磁盤(pán)頁(yè)面磁盤(pán)頁(yè)面聚類(lèi)的磁盤(pán)訪問(wèn)性能Hilbert曲線映射的聚類(lèi)性能比Z序映射稍好，因?yàn)樗鼪](méi)有斜線距離，真正體現(xiàn)了空間距離近的對(duì)象存儲(chǔ)的磁盤(pán)頁(yè)面距離也相近；但

35、在精確入口與出口的計(jì)算算法更為復(fù)雜。Z曲線訪問(wèn)方法的算法l Z序方法實(shí)現(xiàn)空間查詢序方法實(shí)現(xiàn)空間查詢n點(diǎn)查詢點(diǎn)查詢使用二分法在排序文件中查找給出的使用二分法在排序文件中查找給出的Z值值基于基于Z值的值的B樹(shù)索引樹(shù)索引n范圍查詢范圍查詢查詢形狀可以翻譯成一組查詢形狀可以翻譯成一組Z值值某些連續(xù)區(qū)域包含的網(wǎng)格單元具有共同的編碼前綴某些連續(xù)區(qū)域包含的網(wǎng)格單元具有共同的編碼前綴任意的連續(xù)區(qū)域需要拆分成幾片上述性質(zhì)的區(qū)域任意的連續(xù)區(qū)域需要拆分成幾片上述性質(zhì)的區(qū)域通常采用近似的方法減少拆分片數(shù)提高效率通常采用近似的方法減少拆分片數(shù)提高效率n最近鄰居查詢最近鄰居查詢Z序距離不能很好地對(duì)應(yīng)原始坐標(biāo)中的空間距離序

36、距離不能很好地對(duì)應(yīng)原始坐標(biāo)中的空間距離可以采用可以采用Z序的序的B樹(shù)來(lái)處理最近鄰居查詢樹(shù)來(lái)處理最近鄰居查詢空間索引l一維搜索碼的索引一維搜索碼的索引nB樹(shù)與樹(shù)與B+樹(shù)樹(shù)多叉樹(shù)，分支數(shù)量受到上下限的限制多叉樹(shù)，分支數(shù)量受到上下限的限制平衡樹(shù)，子樹(shù)的層次差受到限制平衡樹(shù)，子樹(shù)的層次差受到限制n區(qū)別區(qū)別內(nèi)部節(jié)點(diǎn)是否存儲(chǔ)實(shí)際的搜索碼值內(nèi)部節(jié)點(diǎn)是否存儲(chǔ)實(shí)際的搜索碼值是否允許順序索引是否允許順序索引一維搜索碼的索引：B樹(shù)l動(dòng)態(tài)的結(jié)構(gòu)動(dòng)態(tài)的結(jié)構(gòu)-結(jié)點(diǎn)關(guān)鍵字結(jié)點(diǎn)關(guān)鍵字-結(jié)點(diǎn)可分裂、合并結(jié)點(diǎn)可分裂、合并l非葉子結(jié)點(diǎn)的關(guān)鍵字不出現(xiàn)在葉子結(jié)點(diǎn)，關(guān)鍵字非葉子結(jié)點(diǎn)的關(guān)鍵字不出現(xiàn)在葉子結(jié)點(diǎn)，關(guān)鍵字排列是有序的排列是有序的

37、一維搜索碼的索引：B+樹(shù)l B+樹(shù)的分支結(jié)點(diǎn)上關(guān)鍵碼與指向子女的指針總是成對(duì)樹(shù)的分支結(jié)點(diǎn)上關(guān)鍵碼與指向子女的指針總是成對(duì)出現(xiàn)，僅記錄子節(jié)點(diǎn)出現(xiàn)，僅記錄子節(jié)點(diǎn)最大關(guān)鍵碼最大關(guān)鍵碼，稱(chēng)為分界值關(guān)鍵碼，稱(chēng)為分界值關(guān)鍵碼609930405060697989991102030313336 40414346 50515356 60隨機(jī)查找頭指針BTH順序查找頭指針BTH多維索引多維索引l主要內(nèi)容主要內(nèi)容n網(wǎng)格文件網(wǎng)格文件n四分樹(shù)四分樹(shù)nR樹(shù)樹(shù)網(wǎng)格文件l基本思路基本思路n根據(jù)空間維度劃分根據(jù)空間維度劃分k維空間維空間n將每一（將每一（k-1）維平面索引空間劃分為相等或不等的）維平面索引空間劃分為相等或不等的

38、一些小方格網(wǎng)一些小方格網(wǎng)n與每個(gè)格網(wǎng)相關(guān)聯(lián)的空間目標(biāo)存儲(chǔ)到同一磁盤(pán)頁(yè)面與每個(gè)格網(wǎng)相關(guān)聯(lián)的空間目標(biāo)存儲(chǔ)到同一磁盤(pán)頁(yè)面（桶）或多個(gè)磁盤(pán)頁(yè)面（溢出桶）（桶）或多個(gè)磁盤(pán)頁(yè)面（溢出桶）n頁(yè)面的訪問(wèn)地址通過(guò)格網(wǎng)的線性標(biāo)量（數(shù)組下標(biāo)）頁(yè)面的訪問(wèn)地址通過(guò)格網(wǎng)的線性標(biāo)量（數(shù)組下標(biāo)）求得求得網(wǎng)格文件0132401234桶BDACE網(wǎng)格目錄線性標(biāo)量網(wǎng)格數(shù)組FID線性標(biāo)量線性標(biāo)量桶地址桶地址B B2,32,3512512B B2,42,4512512B B3,33,3512512E E2,02,010241024F F2,02,010241024桶桶桶桶桶桶網(wǎng)格文件網(wǎng)格文件l插入目標(biāo)插入目標(biāo)n定位正確的網(wǎng)格單元，獲取

39、桶地址定位正確的網(wǎng)格單元，獲取桶地址n如該桶未滿，則插入目標(biāo)；如該桶已滿，則分裂桶如該桶未滿，則插入目標(biāo)；如該桶已滿，則分裂桶如果兩個(gè)以上網(wǎng)格對(duì)應(yīng)該桶，則分裂桶后在網(wǎng)格目錄中重如果兩個(gè)以上網(wǎng)格對(duì)應(yīng)該桶，則分裂桶后在網(wǎng)格目錄中重新建立網(wǎng)格與桶的對(duì)應(yīng)關(guān)系新建立網(wǎng)格與桶的對(duì)應(yīng)關(guān)系如果一個(gè)網(wǎng)格對(duì)應(yīng)該桶，則須對(duì)該區(qū)域劃分子空間，在如果一個(gè)網(wǎng)格對(duì)應(yīng)該桶，則須對(duì)該區(qū)域劃分子空間，在k-1維平面上擴(kuò)展。維平面上擴(kuò)展。l刪除目標(biāo)刪除目標(biāo)n定位格網(wǎng)，獲取桶地址，刪除桶內(nèi)目標(biāo)定位格網(wǎng)，獲取桶地址，刪除桶內(nèi)目標(biāo)n合并桶：本桶內(nèi)數(shù)據(jù)與相鄰?fù)皵?shù)據(jù)合計(jì)小于某一閾合并桶：本桶內(nèi)數(shù)據(jù)與相鄰?fù)皵?shù)據(jù)合計(jì)小于某一閾值。值。閾值的設(shè)定是為了防止頻繁分裂或合并閾值的設(shè)定是為了防止頻繁分裂或合并網(wǎng)格文件的特性分析網(wǎng)格文件的特性分析l索引低維度空間（點(diǎn)），可以通過(guò)兩次外存訪問(wèn)索引低維度空間（點(diǎn)），可以通過(guò)兩次外存訪問(wèn)得到結(jié)果，效率較高。得到結(jié)果，效率較高。n網(wǎng)格目錄，得到桶地址網(wǎng)格目錄，得到桶地址n訪問(wèn)桶，得到數(shù)據(jù)訪問(wèn)桶，得到數(shù)據(jù)l網(wǎng)格目錄的存儲(chǔ)網(wǎng)格目錄的存儲(chǔ)n空間維度較高或空間數(shù)據(jù)量較大時(shí)，網(wǎng)格目錄將變空間維度較高或空間數(shù)據(jù)量較大時(shí)，網(wǎng)格目錄將變得非常龐大得非常龐大,桶的分裂將不斷