【正文】 ? 主數(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 – 一個或多個 包含事務日志 數(shù)據(jù)庫在磁盤上是以文件為單位存儲的 ， 由 數(shù)據(jù)庫文件 和 事務日志文件 組成 ， 一個數(shù)據(jù)庫至少應該包含一個數(shù)據(jù)庫文件和一個事務日志文件 數(shù)據(jù)庫文件 ? 1． 主數(shù)據(jù)庫文件 （ Primary Database File） ? 一個數(shù)據(jù)庫可以有一個或多個數(shù)據(jù)庫文件 ，一個數(shù)據(jù)庫文件只能屬于一個數(shù)據(jù)庫 。 ? 數(shù)據(jù)庫的邏輯存儲結(jié)構(gòu)指的是數(shù)據(jù)庫是由哪些性質(zhì)的信息所組成 。 這是許多空間數(shù)據(jù)庫選擇 R樹作為空間索引的一個主要原因 。 這使其具有很強的靈活性和可調(diào)節(jié)性 。 空間要素插入順序的不同會形成不同結(jié)構(gòu)的 R樹 ， 所以隨著空間要素的頻繁插入和刪除 ， 會將 R樹的查詢效率帶向不可預知的方向 。 讓 R樹的結(jié)構(gòu)盡可能的合理是一個非常復雜的問題 。 在插入操作時 ， 選擇插入空間要素后外包絡矩形面積增長最小的結(jié)點為根結(jié)點的子樹 。由于衡量的方法不一樣 ， 由此產(chǎn)生了眾多的 R樹的變型 。插入操作中選擇子樹的標準 ， 分裂操作中的分裂算法 ， 都為了體現(xiàn)這一目標 。 R樹分析 ? R樹讓空間上靠近的空間要素擁有盡可能近的共同祖先 ， 提高 R樹的查詢效率 。 最后將因進行結(jié)點調(diào)整而被刪除的空間要素重新插入到 R樹中 。 如果刪除后該葉子結(jié)點單元個數(shù)少于m， 需要進行 R樹的壓縮操作 ， 將單元數(shù)過少的結(jié)點刪除 。 查詢方式利用了 R樹的結(jié)構(gòu)特征 ， 減少了檢索的范圍 ， 提高了檢索的效率 。 ? 從 R樹中刪除一個空間要素與插入類似 ， 首先從 R樹中查找到記錄該空間要素所在的葉子結(jié)點 ， 這就是 R樹的查找 。 如果這樣引起父結(jié)點的溢出 ， 則繼續(xù)對父結(jié)點進行分裂操作 。 分裂操作是將溢出的結(jié)點按照一定的規(guī)則分為若干部分 。 首先從根結(jié)點出發(fā) ， 按照一定的標準 ， 選擇其中一個孩子插入新的空間要素 ， 然后再從以孩子為根的子樹的根結(jié)點出發(fā)重復操作 ， 直到葉子結(jié)點 。 注意 ， 空間要素相關(guān)的信息只存在葉結(jié)點上 。 葉結(jié)點中存儲該結(jié)點對應的空間要素的外包絡矩形和空間要素標識 ， 這個外包絡矩形是個廣義上的概念 ， 二維上是矩形 ， 三維空間上就是長方體 ，以此類推到高維空間 。 R樹是一種動態(tài)索引結(jié)構(gòu) ， 即：它的查詢可與插入或刪除同時進行 ， 而且不需要定期地對樹結(jié)構(gòu)進行重新組織 。 R樹 ? R樹是 B樹向多維空間發(fā)展的另一種形式 ， 它將空間對象按范圍劃分 ， 每個結(jié)點都對應一個區(qū)域和一個磁盤頁 ， 非葉結(jié)點的磁盤頁中存儲其所有子結(jié)點的區(qū)域范圍 ， 非葉結(jié)點的所有子結(jié)點的區(qū)域都落在它的區(qū)域范圍之內(nèi)；葉結(jié)點的磁盤頁中存儲其區(qū)域范圍之內(nèi)的所有空間對象的外接矩形 。 Child_Pointer 指向該結(jié)點的子結(jié)點 。 其中 ， Index表示包圍空間數(shù)據(jù)對象的最小外接矩形MBR， Obj_ID標識一個空間數(shù)據(jù)對象 。 每一個結(jié)點由若干個索引項構(gòu)成 。 ? R樹是一種用于處理多維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu) ， 用來訪問二維或者更高維區(qū)域?qū)ο蠼M成的空間數(shù)據(jù) .R樹是一棵平衡樹 。 什么樣的結(jié)構(gòu)比較優(yōu)呢 ？ 有兩標準： ? （ 1） 位置上相鄰的結(jié)點盡量在樹中聚集為一個父結(jié)點 。 ? （ 4） 非葉結(jié)點的矩形為所有子結(jié)點矩形的外包矩形 。 ? （ 2） 每個結(jié)點對應一個矩形 。 多維索引： R樹 ? R樹是平衡樹 ， 非常像 B樹 ， 也具有 B樹的一些性質(zhì) 。 并且這種索引機制空間要素的插入和刪除都較簡單 ， 只需在其覆蓋的葉結(jié)點和按照上面的規(guī)則得到父親和祖先結(jié)點中記錄或刪除其標識即可 ， 沒有像 R樹一樣的復雜耗時的分裂和重新插入操作 。 ? （ 2） 索引分析 基于網(wǎng)格劃分的四叉樹索引的構(gòu)成方式與網(wǎng)格索引有些類似 ， 都是多對多的形式 ， 即一個網(wǎng)格可以對應多個空間要素 ， 同時一個空間要素也可以對應多個網(wǎng)格 。 基于網(wǎng)格的四叉樹 ? （ 1） 索引原理 在基于固定網(wǎng)格空間劃分的四叉樹空間索引機制中 ， 二維空間范圍被劃分為一系列大小相等的棋盤狀矩形 ， 并以此建立 N級四叉樹 。 多維索引： 四叉樹 ? 四叉樹空間索引的基本原理是將已知的空間范圍劃成四個相等的子空間 ， 將每個或其中幾個子空間繼續(xù)按照一分為四的原則劃分下去 ， 這樣就形成了一個基于四叉樹的空間劃分 。 然后返回到根的右結(jié)點 ,然后根據(jù)年齡 47 的判斷 ,對它的左結(jié)點只需向左搜索一直到葉結(jié)點 ,找到記錄 (30,260)不符合查詢范圍 。 在根結(jié)點 ,薪水范圍跨越了 $ 1 5 0 K , 因此考察它的兩個子結(jié)點 。 ? 范圍查詢 就是給定一個范圍 ,允許移動到結(jié)點的唯一的一個子結(jié)點 ,如果范圍跨越了結(jié)點的劃分值 ,那么我們就必須考察兩個子結(jié)點 。 例如 ，我們找 KD樹中所有年齡為 50的記錄 ， 因為根是按薪水來分裂的 ， 所以考察根的兩個子結(jié)點 。 此時 ， 若此結(jié)點的兄弟結(jié)點內(nèi)也只有一個記錄 ,則可以將兩個結(jié)點進行合并成為一個結(jié)點 ,以節(jié)省空間 。 如果是葉結(jié)點 ， 則直接刪除即可 。 KD刪除 ? 若實現(xiàn)一個結(jié)點的刪除 ， 首先考慮是內(nèi)部結(jié)點還是葉結(jié)點 。 第四層按 Y 坐標值來分 ， 為能夠均勻劃分這些記錄 ， 我們?nèi)≈虚g值 35 作為新的內(nèi)結(jié)點 。 因此我們被引向包含點 (25， 400)和(45， 350)的葉結(jié)點 ， 新結(jié)點 (35， 500)需插入該塊 。 KD插入 ? 例如某年齡為 35 且薪水為 ￥ 500K 的顧客加入 。并根據(jù)分裂葉結(jié)點的所在層的相應屬性劃分葉結(jié)點中的內(nèi)容 。 KD ? KD樹的更新對于 KD樹的查找 ， 跟二叉樹一樣 ，在每個內(nèi)部結(jié)點上決定了沿哪個走向 ， 最終搜索到所查找的結(jié)點的塊 ， 或者是搜索失敗 ， 沒有查找到相應的葉結(jié)點 。 數(shù)據(jù)庫中有 12 個顧客 。 ? (5)共屬同一個父結(jié)點的兩個結(jié)點互稱為兄弟結(jié)點 。 ? (1)在二維空間中 (2D 樹 )討論； ? (2)根的深度為 0， 在根和偶數(shù)層比較 X坐標值 ， 在奇數(shù)層比較 Y 坐標值 。 設每個數(shù)據(jù)點用樹中一個結(jié)點來表示 ， 每個記錄是通過結(jié)點中的六個域表現(xiàn)出來 。 它的每一層通過檢測不同的屬性 (關(guān)鍵字 )值以決定選擇分枝的方向 。 kd樹 ? KD 樹就是一個二叉數(shù) ,它的內(nèi)部結(jié)點有一個相關(guān)聯(lián)的屬性 a 和一個屬性 V，它將數(shù)據(jù)點分成兩個部分： a 值小于 V 的部分和 a 值大于等于 V 的部分 。 何時使用聚集索引或非聚集索引 稠密索引 ? 文件中的每個搜索碼值都有一個索引記錄 稀疏索引 ? 只為搜索碼的某些值建立索引記錄 多層索引 ? 對索引建立索引 B+樹 ? 樹結(jié)點 ? Ki是搜索碼 ， Pi是指針 B+樹 ? 每個非葉結(jié)點有 [n/2]到 n個子女 B+樹 ? 插入導致結(jié)點分裂 插入 Clearview B+樹 B+樹 ? 刪除導致結(jié)點合并 刪除 Downtown B+樹 散列索引 ? 桶 (bucket) ? 存儲一條或多條記錄的存儲單元 ? 散列 (hash) ? K是搜索碼 ， B是桶地址 ， 散列函數(shù) h(K)=B ? 散列函數(shù) ? 分布是均勻的 ， 桶包含記錄的個數(shù)是均勻的 ? 分布是隨機的 ， 散列值不能與搜索碼的值呈現(xiàn)出相關(guān)性 ? 桶溢出 (bucket overflow) ? 桶不足 (insufficient bucket)+偏斜 (skew) 散列索引 散列索引 ? 溢出鏈 位圖索引 ? 針對一些特殊的列建立索引 ? 列中的每一個值對應一個向量中的一位 ? 向量的長度對應與記錄的條數(shù) ? 不適合列中值的個數(shù)太多的情況 C u st R eg i o n T yp eC1 As ia R et ailC2 Europ e D ealerC3 As ia D ealerC4 Am eric a R et ailC5 Europ e D ealerR ecI D R etai l D eal er1 1 02 0 13 0 14 1 05 0 1R ec I D A si a Eu r o p e A m er i ca1 1 0 02 0 1 03 1 0 04 0 0 15 0 1 0Base table Index on Region Index on Type 位圖索引 ? 查詢： ? Select cust From BaseTable Where Region=‘Asia’ and Type=‘Dealer’； ? BitMap for Region(Asia): 10100 ? BitMap for Type(Dealer): 01101 ? 查詢結(jié)果：向量與操作： 00100 位圖索引 與 B樹的大小對比 位圖索引 ? 設表中有 10M個記錄 ， 每個記錄長 800字節(jié) ， 每一頁16K字節(jié) ， 則掃描此表共需 50萬次 I/O操作 “在美國加州有多少男性未申請保險？” G e n d e r M M F M M 8 0 0 B y t e s / R o w 10M R O W S S t a t e NY CA CT MA CA 傳統(tǒng) R D B M S 作法 傳統(tǒng) R D B M S 做法 I n s u r e d Y Y N Y N 800 By tes x 1 0M R o w s 16K / P ag e = 5 0 0 ,0 0 0 I / O s ? ? 處理大量的數(shù)據(jù) ? ? 經(jīng)常進行全表掃描 位圖索引 ? 對于 10M 個記錄建立三列的位圖索引共占（ 10Mbit*3列 /8)字節(jié)的空間 ， 每頁 16K， 則這些索引僅占 235頁 ， 因此存取這些索引只要 235次 I/O操作 M Y CA M N CA F Y NY M N CA 1 2 4 3 G e n d e r I n s u r e d S ta te = 2 + + 1 1 0 1 1 1 0 1 0 1 0 1 10 M B i t s 10 M B i t s / 8 x 3 C o l s 16 K P a g e = 2 35 I/O s 位圖索引 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 M F R1 0 1 R2 1 0 R3 0 1 R4 0 1 R5 1 0 R6 0 1 R7 1 0 R8 1 0 RID a b c d R1 1 0 0 0 R2 1 0 0 0 R3 0 1 0 0 R4 0 1 0 0 R5 0 1 0 0 R6 0 0 1 0 R7 0 0 1 0 R8 0 0 0 1 基本表 Item位圖索引 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