空間存儲(chǔ)和索引

《空間存儲(chǔ)和索引》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、2021/7/15第四章空間存儲(chǔ)和索引　續(xù)武漢理工大學(xué)資源與環(huán)境工程學(xué)院規(guī)劃系2021/7/152空間存儲(chǔ)和索引目標(biāo)和基本思想物理存儲(chǔ)介質(zhì)緩沖區(qū)管理存儲(chǔ)組織存取路徑：索引結(jié)構(gòu)2021/7/153索引索引：支持對(duì)于所要求的數(shù)據(jù)進(jìn)行快速定位的附加的數(shù)據(jù)結(jié)構(gòu)。每個(gè)索引結(jié)構(gòu)有一個(gè)特定的搜索碼與之關(guān)聯(lián)。索引按一定的方式存儲(chǔ)搜索碼的值，并將搜索碼與包含該搜索碼的記錄關(guān)聯(lián)起來(lái)。搜索碼：用于在文件中查找記錄的屬性或?qū)傩约?021/7/154基本索引結(jié)構(gòu)順序索引索引基于對(duì)搜索碼值的一種排序散列索引索引基于將搜索碼值平均分布到若干

2、散列桶（hashbuckets）中2021/7/155基本索引結(jié)構(gòu)：順序索引順序索引中按照一定的順序存儲(chǔ)搜索碼的值主索引：若文件中的記錄按照某個(gè)搜索碼值的順序來(lái)存儲(chǔ)，則這個(gè)搜索碼所對(duì)應(yīng)的索引稱(chēng)作主索引，或者聚類(lèi)索引（clusterindex）輔助索引：索引對(duì)應(yīng)的搜索碼值的順序與文件記錄的存儲(chǔ)順序不一致，也稱(chēng)作非聚集索引2021/7/156基本索引結(jié)構(gòu)：散列索引在外存中按照桶散列，通過(guò)散列函數(shù)將搜索碼值對(duì)應(yīng)到桶地址桶（bucket）是能存儲(chǔ)一條或多條記錄的一個(gè)存儲(chǔ)單位，每個(gè)桶包括一個(gè)或多個(gè)磁盤(pán)塊散列犧牲存儲(chǔ)效率可以

3、通過(guò)可擴(kuò)充散列，在數(shù)據(jù)庫(kù)大小變化時(shí)對(duì)桶進(jìn)行分裂或合并，保持一定的空間效率2021/7/157散列(hashed)索引散列索引，也稱(chēng)為哈希索引。它既是一種查找方法，又是一種存貯方法，稱(chēng)為散列存貯。散列存貯的內(nèi)存存放形式也稱(chēng)為散列表。散列查找，是通過(guò)構(gòu)造散列函數(shù)來(lái)得到待查關(guān)鍵字的地址，按理論分析真正不需要用到比較的一種查找方法。例如，要找關(guān)鍵字為k的元素，則只需求出函數(shù)值H（k），H（k）為給定的散列函數(shù)，代表關(guān)鍵字k在存貯區(qū)中的地址，而存貯區(qū)為一塊連續(xù)的內(nèi)存單元，可用一個(gè)一維數(shù)組(或鏈表)來(lái)表示。2021/7/15

4、8散列(hashed)索引例1，假設(shè)有一批關(guān)鍵字序列18,75,60,43,54,90,46，給定散列函數(shù)H（k）=k%13，存貯區(qū)的內(nèi)存地址從0到15，則可以得到每個(gè)關(guān)鍵字的散列地址為：H（18）=18%13=5H（75）=75%13=10H（60）=60%13=8H（43）=43%13=4H（54）=54%13=2H（90）=90%13=12H（46）=46%13=7于是，根據(jù)散列地址，可以將上述7個(gè)關(guān)鍵字序列存貯到一個(gè)一維數(shù)組HT（散列表）中，具體表示為：2021/7/159其中HT就是散列存貯的表，稱(chēng)為散

5、列表。從散列表中查找一個(gè)元素相當(dāng)方便，例如，查找75，只需計(jì)算出H（75）=75%13=10，則可以在HT[10]中找到75。544318466075900123456789101112131415HT散列(Hashing)在線(xiàn)性表、樹(shù)結(jié)構(gòu)中查找記錄是通過(guò)與關(guān)鍵字的“比較”完成的。順序查找，比較的結(jié)果為“=”或“≠”非順序查找，比較的結(jié)果為“<”，“=”，“>”基本概念散列:由關(guān)鍵字通過(guò)確定的對(duì)應(yīng)關(guān)系計(jì)算得到記錄的存儲(chǔ)位置的過(guò)程稱(chēng)散列。哈希表:按散列形式的記錄的集合稱(chēng)散列表或哈希表。所使用的對(duì)應(yīng)關(guān)系稱(chēng)散列函數(shù)或哈

6、希函數(shù)散列查找：也稱(chēng)哈希查找，是由關(guān)鍵字通過(guò)計(jì)算得到記錄存儲(chǔ)地址的查找方法。沖突：通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過(guò)哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上，這種現(xiàn)象稱(chēng)為沖突。例：有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k的存儲(chǔ)地址H（k）＝k，請(qǐng)畫(huà)出存儲(chǔ)結(jié)構(gòu)圖。解：根據(jù)散列函數(shù)H（k）＝k，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，……，對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)表達(dá)式，即可查到結(jié)果！例如，查

7、找key=9,則訪(fǎng)問(wèn)H(9)=9號(hào)地址，若內(nèi)容為9則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或空記錄。地址…9…11…14…232425…39…內(nèi)容14119232539明顯缺點(diǎn)：空間效率低有6個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過(guò)哈希函數(shù)對(duì)6個(gè)元素建立哈希表：253923914沖突現(xiàn)象舉例：6個(gè)元素用7個(gè)地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！0123456所以，哈希方

8、法必須解決以下兩個(gè)問(wèn)題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址內(nèi)集中并大致均勻分布，以減少空間浪費(fèi)。2）制定一個(gè)好的解決沖突的方案查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢(xún)其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。常用的哈希函數(shù)