【正文】 Gender 位圖索引 編碼位圖索引 RID Item Gender R1 a F R2 a M R3 b F R4 b F R5 b M R6 c F R7 c M R8 d M RID B1 B0 R1 0 0 R2 0 0 R3 0 1 R4 0 1 R5 0 1 R6 1 0 R7 1 0 R8 1 1 基本表 Item編碼位圖索引 Item值 編碼值 a 00 b 01 c 10 d 11 映射表 簡單位圖需要 4個向量，編碼位圖需要 log24=2個 編碼位圖索引 如果屬性 I的取值 v0被編碼為 b1b0， 檢索函數(shù)被定義為 x1x0， 其中如果 bi=1， 則 xi=Bi， 否則 xi=B’i(B’i為 Bi的非 ) 檢索函數(shù) fa = B’1B’0 ， fb = B’1B0 fc = B1B’0 ， fd = B1B0 如果檢索取值為 a或 b的元組 ， fa or fb = B’1B’0 or B’1B0 = B’1 位片索引 (Bitsliced Index) ? 位片索引是將屬性列的域值按照某種方式進行垂直分割 ， 然后以二進制位圖的形式存儲 S ale s i n b in ar y f o rm8 b it 4 b it 2 b i t 1 b it0 1 1 01 0 0 10 1 0 11 0 1 11 0 0 10 0 1 10 1 1 11 1 0 0S ale s6951193712S ale s i n b in ar y f o rm0 1 1 01 0 0 10 1 0 11 0 1 11 0 0 10 0 1 10 1 1 11 1 0 0位片索引 3/1 3/1 3/1 3/1 3/1 3/1 3/1 3/1 32 36 38 41 43 46 47 49 NY MA NY CT NY RI CT NY A A B A A B B A 6 9 5 11 9 3 7 12 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0 date store state class sales state = NY class =A sales in binary form 8 4 2 1 select sum(sales) from customers where state=‘NY’ and class=‘A’ 多維索引 ? 空間數(shù)據(jù) 多維索引 ? 空間查詢 ? 臨近查詢 查詢位于特定位臵附近的對象 ? 最近鄰查詢 (nearest neighbor query) 查詢離特定位臵最近的對象 ? KNN 查詢離特定位臵最近的 k個對象 ? 區(qū)域查詢 查詢位于指定區(qū)域內(nèi)的對象 空間索引 ? 空間索引是對存儲在介質(zhì)上的數(shù)據(jù)位置信息的描述 ，用來提高系統(tǒng)對數(shù)據(jù)獲取的效率 。 它的每一層通過檢測不同的屬性 (關(guān)鍵字 )值以決定選擇分枝的方向 。 ? (1)在二維空間中 (2D 樹 )討論； ? (2)根的深度為 0， 在根和偶數(shù)層比較 X坐標值 ， 在奇數(shù)層比較 Y 坐標值 。 數(shù)據(jù)庫中有 12 個顧客 。并根據(jù)分裂葉結(jié)點的所在層的相應(yīng)屬性劃分葉結(jié)點中的內(nèi)容 。 因此我們被引向包含點 (25， 400)和(45， 350)的葉結(jié)點 ， 新結(jié)點 (35， 500)需插入該塊 。 KD刪除 ? 若實現(xiàn)一個結(jié)點的刪除 ， 首先考慮是內(nèi)部結(jié)點還是葉結(jié)點 。 此時 ， 若此結(jié)點的兄弟結(jié)點內(nèi)也只有一個記錄 ,則可以將兩個結(jié)點進行合并成為一個結(jié)點 ,以節(jié)省空間 。 ? 范圍查詢 就是給定一個范圍 ,允許移動到結(jié)點的唯一的一個子結(jié)點 ,如果范圍跨越了結(jié)點的劃分值 ,那么我們就必須考察兩個子結(jié)點 。 然后返回到根的右結(jié)點 ,然后根據(jù)年齡 47 的判斷 ,對它的左結(jié)點只需向左搜索一直到葉結(jié)點 ,找到記錄 (30,260)不符合查詢范圍 。 基于網(wǎng)格的四叉樹 ? （ 1） 索引原理 在基于固定網(wǎng)格空間劃分的四叉樹空間索引機制中 ， 二維空間范圍被劃分為一系列大小相等的棋盤狀矩形 ， 并以此建立 N級四叉樹 。 并且這種索引機制空間要素的插入和刪除都較簡單 ， 只需在其覆蓋的葉結(jié)點和按照上面的規(guī)則得到父親和祖先結(jié)點中記錄或刪除其標識即可 ， 沒有像 R樹一樣的復(fù)雜耗時的分裂和重新插入操作 。 ? （ 2） 每個結(jié)點對應(yīng)一個矩形 。 什么樣的結(jié)構(gòu)比較優(yōu)呢 ？ 有兩標準： ? （ 1） 位置上相鄰的結(jié)點盡量在樹中聚集為一個父結(jié)點 。 每一個結(jié)點由若干個索引項構(gòu)成 。 Child_Pointer 指向該結(jié)點的子結(jié)點 。 R樹是一種動態(tài)索引結(jié)構(gòu) ， 即：它的查詢可與插入或刪除同時進行 ， 而且不需要定期地對樹結(jié)構(gòu)進行重新組織 。 注意 ， 空間要素相關(guān)的信息只存在葉結(jié)點上 。 分裂操作是將溢出的結(jié)點按照一定的規(guī)則分為若干部分 。 ? 從 R樹中刪除一個空間要素與插入類似 ， 首先從 R樹中查找到記錄該空間要素所在的葉子結(jié)點 ， 這就是 R樹的查找 。 如果刪除后該葉子結(jié)點單元個數(shù)少于m， 需要進行 R樹的壓縮操作 ， 將單元數(shù)過少的結(jié)點刪除 。 R樹分析 ? R樹讓空間上靠近的空間要素擁有盡可能近的共同祖先 ， 提高 R樹的查詢效率 。由于衡量的方法不一樣 ， 由此產(chǎn)生了眾多的 R樹的變型 。 讓 R樹的結(jié)構(gòu)盡可能的合理是一個非常復(fù)雜的問題 。 這使其具有很強的靈活性和可調(diào)節(jié)性 。 ? 數(shù)據(jù)庫的邏輯存儲結(jié)構(gòu)指的是數(shù)據(jù)庫是由哪些性質(zhì)的信息所組成 。 ? 主數(shù)據(jù)庫文件。 SQL Server存儲結(jié)構(gòu) ? 文件結(jié)構(gòu) ? 表結(jié)構(gòu) ? 行結(jié)構(gòu) ? 索引結(jié)構(gòu) 文件 ? 一個數(shù)據(jù)庫是操作系統(tǒng)文件的集合 ? 數(shù)據(jù)庫之間不能進行文件共享 ? 一個數(shù)據(jù)庫至少包括一個數(shù)據(jù)文件和一個日志文件 ? 每個數(shù)據(jù)庫最多 32,767個文件 ? 數(shù)據(jù)和日志文件一般不能放在同一驅(qū)動器上 文件 ? 文件類型 ? 主數(shù)據(jù)文件 .mdf – 每個數(shù)據(jù)庫一個 目錄表 sysfiles必須完全包含在此文件中 ? 輔助數(shù)據(jù)文件 .ndf – 零個或多個 ? 日志文件 .ldf – 一個或多個 包含事務(wù)日志 數(shù)據(jù)庫在磁盤上是以文件為單位存儲的 ， 由 數(shù)據(jù)庫文件 和 事務(wù)日志文件 組成 ， 一個數(shù)據(jù)庫至少應(yīng)該包含一個數(shù)據(jù)庫文件和一個事務(wù)日志文件 數(shù)據(jù)庫文件 ? 1． 主數(shù)據(jù)庫文件 （ Primary Database File） ? 一個數(shù)據(jù)庫可以有一個或多個數(shù)據(jù)庫文件 ，一個數(shù)據(jù)庫文件只能屬于一個數(shù)據(jù)庫 。 這是許多空間數(shù)據(jù)庫選擇 R樹作為空間索引的一個主要原因 。 空間要素插入順序的不同會形成不同結(jié)構(gòu)的 R樹 ， 所以隨著空間要素的頻繁插入和刪除 ， 會將 R樹的查詢效率帶向不可預(yù)知的方向 。 在插入操作時 ， 選擇插入空間要素后外包絡(luò)矩形面積增長最小的結(jié)點為根結(jié)點的子樹 。插入操作中選擇子樹的標準 ， 分裂操作中的分裂算法 ， 都為了體現(xiàn)這一目標 。 最后將因進行結(jié)點調(diào)整而被刪除的空間要素重新插入到 R樹中 。 查詢方式利用了 R樹的結(jié)構(gòu)特征 ， 減少了檢索的范圍 ， 提高了檢索的效率 。 如果這樣引起父結(jié)點的溢出 ， 則繼續(xù)對父結(jié)點進行分裂操作 。 首先從根結(jié)點出發(fā) ， 按照一定的標準 ， 選擇其中一個孩子插入新的空間要素 ， 然后再從以孩子為根的子樹的根結(jié)點出發(fā)重復(fù)操作 ， 直到葉子結(jié)點 。 葉結(jié)點中存儲該結(jié)點對應(yīng)的空間要素的外包絡(luò)矩形和空間要素標識 ， 這個外包絡(luò)矩形是個廣義上的概念 ， 二維上是矩形 ， 三維空間上就是長方體 ，以此類推到高維空間 。 R樹 ? R樹是 B樹向多維空間發(fā)展的另一種形式 ， 它將空間對象按范圍劃分 ， 每個結(jié)點都對應(yīng)一個區(qū)域和一個磁盤頁 ， 非葉結(jié)點的磁盤頁中存儲其所有子結(jié)點的區(qū)域范圍 ， 非葉結(jié)點的所有子結(jié)點的區(qū)域都落在它的區(qū)域范圍之內(nèi)；葉結(jié)點的磁盤頁中存儲其區(qū)域范圍之內(nèi)的所有空間對象的外接矩形 。 其中 ， Index表示包圍空間數(shù)據(jù)對象的最小外接矩形MBR， Obj_ID標識一個空間數(shù)據(jù)對象 。 ? R樹是一種用于處理多維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu) ， 用來訪問二維或者更高維區(qū)域?qū)ο蠼M成的空間數(shù)據(jù) .R樹是一棵平衡樹 。 ? （ 4） 非葉結(jié)點的矩形為所有子結(jié)點矩形的外包矩形 。 多維索引： R樹 ? R樹是平衡樹 ， 非常像 B樹 ， 也具有 B樹的一些性質(zhì) 。 ? （ 2） 索引分析 基于網(wǎng)格劃分的四叉樹索引的構(gòu)成方式與網(wǎng)格索引有些類似 ， 都是多對多的形式 ， 即一個網(wǎng)格可以對應(yīng)多個空間要素 ， 同時一個空間要素也可以對應(yīng)多個網(wǎng)格 。 多維索引： 四叉樹 ? 四叉樹空間索引的基本原理是將已知的空間范圍劃成四個相等的子空間 ， 將每個或其中幾個子空間繼續(xù)按照一分為四的原則劃分下去 ， 這樣就形成了一個基于四叉樹的空間劃分 。 在根結(jié)點 ,薪水范圍跨越了 $ 1 5 0 K , 因此考察它的兩個子結(jié)點 。 例如 ，我們找 KD樹中所有年齡為 50的記錄 ， 因為根是按薪水來分裂的 ， 所以考察根的兩個子結(jié)點 。 如果是葉結(jié)點 ， 則直接刪除即可 。 第四層按 Y 坐標值來分 ， 為能夠均勻劃分這些記錄 ， 我們?nèi)≈虚g值 35 作為新的內(nèi)結(jié)點 。 KD插入 ? 例如某年齡為 35 且薪水為 ￥ 500K 的顧客加入 。 KD ? KD樹的更新對于 KD樹的查找 ， 跟二叉樹一樣 ，在每個內(nèi)部結(jié)點上決定了沿哪個走向 ， 最終搜索到所查找的結(jié)點的塊 ， 或者是搜索失敗 ， 沒有查找到相應(yīng)的葉結(jié)點 。 ? (5)共屬同一個父結(jié)點的兩個結(jié)點互稱為兄弟結(jié)點 。 設(shè)每個數(shù)據(jù)點用樹中一個結(jié)點來表示 ， 每個記錄是通過結(jié)點中的六個域表現(xiàn)出來 。 kd樹 ? KD 樹就是一個二叉數(shù) ,它的內(nèi)部結(jié)點有一個相關(guān)聯(lián)的屬性 a 和一個屬性 V，它將數(shù)據(jù)點分成兩個部分： a 值小于 V 的部分和 a 值大于等于 V 的部分 。 非聚集索引比聚集索引層次多 ， 添加記錄不會引起數(shù)據(jù)順序的重組 。 比較 ? 聚集索引和非聚集索引的 根本區(qū)別是表記錄的排列順序和與索引的排列順序是否一致 ， 聚集索引表記錄的排列順序與索引的排列順序一致 ， 優(yōu)點是查詢速度快 ， 因為一旦具有第一個索引值的紀錄被找到 ， 具有連續(xù)索引值的記錄也一定物理的緊跟其后 。 例如 ， 對于在 emp_id 列上有非聚集索引的表 ， 如要搜索其雇員 ID (emp_id)， SQL Server 會在索引中查找這樣一個條目 ， 該條目精確列出匹配的 emp_id 列在表中的頁和行 ， 然后直接轉(zhuǎn)到該頁該行 。 索引中的項目按索引鍵值的順序存儲 ， 而表中的信息按另一種順序存儲 。 ? 說明 如果該表上尚未創(chuàng)建聚集索引 ， 且在創(chuàng)建 PRIMARY KEY 約束時未指定非聚集索引 ，PRIMARY KEY 約束會自動創(chuàng)建聚集索引 。這樣有助于提高此類查詢的性能 。 因此一個表只能包含一個聚集索引 。 ? 如果一個表聲明了一個唯一約束或者一個主鍵 ， 那么 SQL 自動在那些組成主鍵或者唯一字段的列上創(chuàng)建唯一索引 (可能地話是一個多字段索引 )， 以強迫這些約束 。 目前 ， 只有 Btree 索引可以聲明為唯一的 。 ? 注意：主索引是數(shù)據(jù)庫表的整體部分 。 ? 其它類似用到緩沖區(qū)的設(shè)計 （ 當(dāng)緩存不足以放下所有數(shù)據(jù)或為了節(jié)省內(nèi)存 ） ， 均可參考此種替換策略 。如果計數(shù)器的值不為零 ， 系統(tǒng)則將計數(shù)器的值減少 。 ? 7 0 1 2 0 3 0 4 2