5-空間存儲和索引解析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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