【正文】 ? 插入時(shí)間 ? 刪除時(shí)間 ? 空間開銷 主索引和輔助索引 ? 主索引 (primary index)、 輔助索引 (secondary index)；聚集索引 (cluster index)、 非聚集索引(noncluster index) branch_name balance 主索引 ? 主索引包含表中每條記錄的索引關(guān)鍵字并且當(dāng)未指定任何其他索引作為表主索引時(shí)的默認(rèn)索引 。 該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面 ， 按先后次序鏈接成一個(gè)隊(duì)列 ， 并設(shè)置一個(gè)指針 ， 稱為替換指針 ， 使它總是指向最老的頁(yè)面 。 因此即使是當(dāng)前硬盤上的數(shù)據(jù)塊損壞 ， 也可以通過 XOR 校驗(yàn)值和其他硬盤上的同級(jí)數(shù)據(jù)進(jìn)行恢復(fù) 。 但由于數(shù)據(jù)是以位為單位并行傳輸 ， 所以傳輸率也相當(dāng)快 。 ? 參照位置表 ， 漢明碼處理的結(jié)果就是 1010101 。 磁盤調(diào)度（ 2） ? SSTF（ 最短查找時(shí)間優(yōu)先 ） 調(diào)度 ? 考慮了各個(gè)請(qǐng)求之間的區(qū)別 ， 總是先執(zhí)行查找時(shí)間最短的那個(gè)請(qǐng)求 。 因此緩存容量的加大可以容納更多的預(yù)讀數(shù)據(jù) ， 這樣大大縮短系統(tǒng)等待的時(shí)間 。 磁盤 ? 磁盤性能度量 ? 訪問時(shí)間：從發(fā)出讀寫請(qǐng)求到數(shù)據(jù)開始傳輸之間的時(shí)間 。 為到達(dá)指定扇區(qū) ， 需要先 移動(dòng) 磁盤臂 ，定位到正確的磁道 ， 然后 旋轉(zhuǎn) 磁盤 ， 直到指定的扇區(qū)出現(xiàn)在讀寫頭下方 ? 尋道時(shí)間 (seek time)：磁盤臂重定位時(shí)間 ， 取決于目標(biāo)磁道和磁盤臂當(dāng)前距離 ， 2~30毫秒 。 目前主流硬盤的緩存通常為 8MB和 16MB。 磁頭從 53號(hào)磁道開始移動(dòng) ， 按照 65, 67, 37, 14, 98, 122, 124, 183 的順序依次查找 ， 并將數(shù)據(jù)輸入內(nèi)存 。 在這里漢明碼都是以三個(gè)數(shù)據(jù)碼為基準(zhǔn)進(jìn)行編碼的 。 ? RAID 2 是早期為了能進(jìn)行即時(shí)的數(shù)據(jù)校驗(yàn)而研制的一種技術(shù) ， 針對(duì)了當(dāng)時(shí)對(duì)數(shù)據(jù)即時(shí)性非常敏感的領(lǐng)域 ， 如 、 金融服務(wù)等 。 ? RAID 4 在寫入時(shí)要等一個(gè)硬盤寫完后才能寫一下個(gè) ， 還要寫入校驗(yàn)數(shù)據(jù)所以寫入效率比較差 ， 讀取時(shí)也是一個(gè)硬盤一個(gè)硬盤的讀 ， 但校驗(yàn)迅速 ，所以相對(duì)速度很快 。 例 ? 在一個(gè)請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中 ， 一個(gè)作業(yè)的頁(yè)面走向?yàn)? 5， 當(dāng)分配給該作業(yè)的物理塊數(shù)分別為 4時(shí) ， 試計(jì)算采用下述頁(yè)面淘汰算法時(shí)的缺頁(yè)次數(shù) (假設(shè)開始執(zhí)行時(shí)主存中沒有頁(yè)面 )， 并比較所得結(jié)果 。 主索引禁止為產(chǎn)生索引關(guān)鍵字所指定字段或索引表達(dá)式中的重復(fù)值；因此 ， 主索引中每個(gè)索引關(guān)鍵字是唯一的 。 ? 聚集索引對(duì)于那些經(jīng)常要搜索范圍值的列特別有效 。 ? 若未指定索引類型 ， 則默認(rèn)為非聚集索引 ? 葉節(jié)點(diǎn)頁(yè)的次序和表的物理存儲(chǔ)次序不同 ? 每個(gè)表最多可以有 249個(gè)非聚集索引 ? 在非聚集索引創(chuàng)建之前創(chuàng)建聚集索引 (否則會(huì)引發(fā)索引重建 ) 非聚集索引 ? select * from employee where lname = 39。 ? (1)在二維空間中 (2D 樹 )討論； ? (2)根的深度為 0， 在根和偶數(shù)層比較 X坐標(biāo)值 ， 在奇數(shù)層比較 Y 坐標(biāo)值 。 KD刪除 ? 若實(shí)現(xiàn)一個(gè)結(jié)點(diǎn)的刪除 ， 首先考慮是內(nèi)部結(jié)點(diǎn)還是葉結(jié)點(diǎn) 。 基于網(wǎng)格的四叉樹 ? （ 1） 索引原理 在基于固定網(wǎng)格空間劃分的四叉樹空間索引機(jī)制中 ， 二維空間范圍被劃分為一系列大小相等的棋盤狀矩形 ， 并以此建立 N級(jí)四叉樹 。 每一個(gè)結(jié)點(diǎn)由若干個(gè)索引項(xiàng)構(gòu)成 。 分裂操作是將溢出的結(jié)點(diǎn)按照一定的規(guī)則分為若干部分 。由于衡量的方法不一樣 ， 由此產(chǎn)生了眾多的 R樹的變型 。 ? 主數(shù)據(jù)庫(kù)文件。 在插入操作時(shí) ， 選擇插入空間要素后外包絡(luò)矩形面積增長(zhǎng)最小的結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹 。 如果這樣引起父結(jié)點(diǎn)的溢出 ， 則繼續(xù)對(duì)父結(jié)點(diǎn)進(jìn)行分裂操作 。 其中 ， Index表示包圍空間數(shù)據(jù)對(duì)象的最小外接矩形MBR， Obj_ID標(biāo)識(shí)一個(gè)空間數(shù)據(jù)對(duì)象 。 ? （ 2） 索引分析 基于網(wǎng)格劃分的四叉樹索引的構(gòu)成方式與網(wǎng)格索引有些類似 ， 都是多對(duì)多的形式 ， 即一個(gè)網(wǎng)格可以對(duì)應(yīng)多個(gè)空間要素 ， 同時(shí)一個(gè)空間要素也可以對(duì)應(yīng)多個(gè)網(wǎng)格 。 如果是葉結(jié)點(diǎn) ， 則直接刪除即可 。 ? (5)共屬同一個(gè)父結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn) 。 比較 ? 聚集索引和非聚集索引的 根本區(qū)別是表記錄的排列順序和與索引的排列順序是否一致 ， 聚集索引表記錄的排列順序與索引的排列順序一致 ， 優(yōu)點(diǎn)是查詢速度快 ， 因?yàn)橐坏┚哂械谝粋€(gè)索引值的紀(jì)錄被找到 ， 具有連續(xù)索引值的記錄也一定物理的緊跟其后 。這樣有助于提高此類查詢的性能 。 ? 注意：主索引是數(shù)據(jù)庫(kù)表的整體部分 。 最近最久未使用 （ LRU）置換算法 ， 是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的 。 ? RAID 1 適合性能要求較高又需要容錯(cuò)功能的陣列 。 P P P RAID 2 ? RAID 2使用共軸同步 (spindle synchronize)技術(shù) ， 存取數(shù)據(jù)時(shí) ,整個(gè)磁盤陣列一起動(dòng)作 ,在各個(gè)磁盤的相同位置作平行存取 ，有最好的存取時(shí)間 (access time)， 以大帶寬 (band wide)并行傳輸所存取的數(shù)據(jù) ， 有最好的傳輸時(shí)間 (transfer time) ? 對(duì)于大型檔案的存取應(yīng)用 ， RAID 2有較好的性能 ， 但如果檔案太小 ， 性能會(huì)下降 ， 因?yàn)榇疟P的存取是以扇區(qū)為單位 ， 而RAID 2的存取是所有磁盤平行動(dòng)作 ， 故小于一個(gè)扇區(qū)的數(shù)據(jù)量會(huì)使其性能大打折扣 ? RAID 2適合于存取連續(xù)且大量數(shù)據(jù)的應(yīng)用 ， 如大型電腦 、 作影像處理或 CAD/CAM的工作站等 RAID 3 ? Parallel transfer with parity （ 并行傳輸及校驗(yàn) ） ? RAID 3 是在 RAID 2 基礎(chǔ)上發(fā)展而來的 ， 主要的變化是用相對(duì)簡(jiǎn)單的異或邏輯運(yùn)算 （ XOR， eXclusive OR ） 校驗(yàn)代替了相對(duì)復(fù)雜的漢明碼校驗(yàn) ， 從而也大幅降低了成本 。 ? 1101， 正確的編碼為 1010101， 如果第三個(gè)數(shù)據(jù)位在傳輸途中 因 干 擾 而 變 成 了 1 ， 就成了 1010111 。 然后調(diào)轉(zhuǎn)方向 ，從此端移動(dòng)到另一端 。 內(nèi)傳輸速率是從硬盤到緩存的傳輸速度 ， 外傳輸速率是從緩存到通信接口的傳輸速度 。平均旋轉(zhuǎn)時(shí)間是旋轉(zhuǎn)一周的 1/2 ? 數(shù)據(jù)傳輸率 (datatransfer rate)， 25~100兆 /秒 磁盤訪問優(yōu)化 ? 磁盤塊的大小 ? 小 ， 更多的磁盤傳輸次數(shù)；大 ， 空間浪費(fèi) ? 調(diào)度 ? 塊在一個(gè)柱面上 ， 按塊經(jīng)過讀寫頭的順序訪問；塊在不同柱面上 ， 按使磁盤臂移動(dòng)距離最短的順序訪問 ? 電梯算法 ? 文件組織 ? 按與預(yù)期數(shù)據(jù)訪問方式最接近的方式組織磁盤塊 ? 碎片整理 ? 日志磁盤 ? 順序?qū)?， 消除了尋道時(shí)間 磁盤的性能指標(biāo) ? （ 1） 容量 ? 磁盤上信息的存儲(chǔ)是以同心圓的形式排列的 ， 每一個(gè)圓稱為一個(gè)磁道 。 構(gòu)成硬盤的每個(gè)碟片都被劃分為數(shù)目相等的磁道 ， 并從外緣的 “ 0”開始編號(hào) ， 具有相同編號(hào)的磁道形成一個(gè)圓柱 ， 稱之為磁盤的柱面 。 在數(shù)據(jù)的讀取過程中 ， 硬盤里的控制芯片發(fā)出指令 ， 將系統(tǒng)指令正在讀取的簇的相鄰的下一個(gè)或幾個(gè)簇的數(shù)據(jù)讀入硬盤高速緩存 。 當(dāng)前硬盤磁頭在第 53號(hào)磁道 。 RAID 1： 無(wú)冗余拆分 C C C C 漢明碼 ? 漢明碼是一個(gè)在原有數(shù)據(jù)中插入若干校驗(yàn)碼來進(jìn)行錯(cuò)誤檢查和糾正的編碼技術(shù) 。 ? 在寫入時(shí) ， RAID 2 在寫入數(shù)據(jù)位同時(shí)還要計(jì)算出它們的漢明碼并寫入校驗(yàn)陣列 ， 讀取時(shí)也要對(duì)數(shù)據(jù)即時(shí)進(jìn)行校驗(yàn) 。 ? 在不同硬盤上的同級(jí)數(shù)據(jù) （ 在每個(gè)硬盤中同一柱面同一扇區(qū)位置的數(shù)據(jù) ）塊也通過 XOR 進(jìn)行校驗(yàn) ， 結(jié)果保存在單獨(dú)的校驗(yàn)盤 。 這是最早出現(xiàn)的置換算法 。 在順序掃描時(shí) ， 這些計(jì)數(shù)器的值不是簡(jiǎn)單的減少 ， 而是以某種策略縮小 （ 如除以 4） ， 這樣可以保證它不會(huì)很快變成零 ， 從而可以在內(nèi)存中貯存較長(zhǎng)時(shí)間 。 主索引 VS唯一索引 ? 主索引一定是唯一索引； ? 唯一索引不一定是主索引； ? 主索引只有一個(gè)； ? 唯一索引可有多個(gè) 聚集索引 (Clustered Index) ? 聚集索引規(guī)定數(shù)據(jù)在表中的物理存儲(chǔ)順序：聚集索引表記錄的排列順序與索引的排列順序一致 。 如果基礎(chǔ)表使用聚集索引排序 ， 則該位置為聚集鍵值；否則 ， 該位置為包含行的文件號(hào) 、 頁(yè)號(hào)和槽號(hào)的行 ID (RID)。 ? 以兩個(gè)屬性的 KD 樹為例 。但是 ， 由于每一塊只能存放兩條記錄 ， 所以我們必須分裂該塊 。然后在 47的右結(jié)點(diǎn)上 ,找到兩條記錄也不符合查詢范圍 。 ? （ 2） 同一層中各兄弟結(jié)點(diǎn)相交部分比例盡量小 。 R樹的插入刪除 ? R樹的插入與其他樹 ， 為一個(gè)遞歸過程 。 在構(gòu)造 R樹的時(shí)候 ， 盡可能讓空間要素的空間位置的遠(yuǎn)近體現(xiàn)在其最近的共同祖先的遠(yuǎn)近上 ， 讓聚集在一起的空間要素盡可能早的組合在一起 。 實(shí)際上 ， SQL Server的數(shù)據(jù)庫(kù)是由諸如表 、 視圖 、 索引 、 約束 、默認(rèn)值 、 規(guī)則 、 觸發(fā)器 、 用戶定義數(shù)據(jù)類型 、用戶定義函數(shù) 、 存儲(chǔ)過程等各種不同的數(shù)據(jù)庫(kù)對(duì)象所組成 。 眾多的方法都不能很完善的衡量空間的聚集 ， 他們都只能做到局部的優(yōu)化 ， 無(wú)法保證由此形成的 R樹的整體結(jié)構(gòu)最優(yōu) 。 從根結(jié)點(diǎn)開始 ， 依次檢索包含空間要素的單元所對(duì)應(yīng)孩子結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹 。 Index仍指一個(gè)矩形區(qū)域 ， 該矩形區(qū)域包圍了子結(jié)點(diǎn)上所有索引項(xiàng) MBR的最小矩形區(qū)域 。 同時(shí) ， 其查詢方式也比較簡(jiǎn)單 ， 例如要檢索某一多邊形內(nèi)和與其邊相交的空間要素 ， 只需先檢索出查詢多邊形所覆蓋的葉結(jié)點(diǎn)和其父親和祖先結(jié)點(diǎn)中所有的空間要素 ， 然后再進(jìn)行必要的空間運(yùn)算 ， 從中檢索出滿足要求的空間要素 。 KD查詢 ? 部分匹配查詢 ， 若給定某些屬性的值 ， 當(dāng)處于屬性值已知的層的節(jié)點(diǎn)上時(shí) ， 根據(jù)比較可以選擇一個(gè)方向往下進(jìn)行；當(dāng)處于屬性值未知的結(jié)點(diǎn)上時(shí) ， 必須考察它的兩個(gè)子結(jié)點(diǎn) 。 把它表示成下列的年齡 —薪水對(duì)： (25,60) (45,60) (50,75) (50,100)(70,110)(85,140) (30,260) (25,400) (50,275) (60,260) (50,120) (45,350)顧客的各種信息存儲(chǔ)在二維表中 ， 我們?cè)O(shè)其表名為CustomerTb， 其中數(shù)據(jù)塊是以年齡代表數(shù)據(jù)記錄 ， 每一塊包含兩個(gè)數(shù)據(jù)記錄 。 比較 ? 非聚集索引指定了表中記錄的邏輯順序 ， 但記錄的物理順序和索引的順序不一致 ， 聚集索引和非聚集索引都采用了 B+樹的結(jié)構(gòu) ， 但非聚集索引的葉子層并不與實(shí)際的數(shù)據(jù)頁(yè)相重疊 ， 而采用葉子層包含一個(gè)指向表中的記錄在數(shù)據(jù)頁(yè)中的指針的方式 。 例如 ， 使用唯一雇員 ID 列 emp_id 查找特定雇員的最快速的方法 ， 是在 emp_id 列上創(chuàng)建聚集索引或 PRIMARY KEY 約束 。 唯一索引 ? 索引還可以用于強(qiáng)迫字段數(shù)值的唯一性 ， 或者是多個(gè)字段組合值的唯一性： CREATE UNIQUE INDEX name ON table (column [, ...])。 LRU ? 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 ? 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7 7 1 1 2 3 0 4 4 4 0 0 3 3 2 2 ? * * * * * * * * ? 缺頁(yè)中斷次數(shù)： 8 LFU ? 最近最少使用淘汰法 LFU(Least Frequently Used) （ 記錄各個(gè)頁(yè)面在最近一段時(shí)間內(nèi)被使用的次數(shù) ， 淘汰使用次數(shù)最少的頁(yè)面 。 ? RAID 5 是在多用戶 ， 對(duì)數(shù)據(jù)寫入的性能要求不高的環(huán)境下的最好選擇 。 讀取時(shí) ， 則在調(diào)出條帶的同時(shí)檢查校驗(yàn)盤中相應(yīng)的 XOR 編碼 ， 進(jìn)行即時(shí)的 ECC。P3+D4+D2+D1 的結(jié)果是奇數(shù) 3， 第三位糾錯(cuò)代碼為 1， 錯(cuò)誤 。 磁頭從 53號(hào)磁道開始移動(dòng) ， 按照 65, 67, 98, 122, 124, 183, 199, 0, 14, 37的順序依次查找 (其中從199——0的過程中不做任何操作只是快速的移