【文章內(nèi)容簡(jiǎn)介】 minute rule： 如果被順序訪問(wèn)的頁(yè)面的使用頻率超過(guò)每 1分鐘一次 ， 那么它應(yīng)該被駐留在內(nèi)存 priceperdiskdrive=2022$/disk accessespersecondperdisk=64accesses/second/disk priceperMBofmemory=15$/MB_RAM pagesperMBofmemory=128pages/MB 2022 * 128/15/64/=266 緩沖區(qū)管理 ? 當(dāng)需要訪問(wèn)一個(gè)磁盤塊時(shí) ? 如果該塊已經(jīng)在緩沖區(qū)中 ， 返回塊在內(nèi)存中的地址 ? 如果塊不在緩沖區(qū)中 ? 緩沖區(qū)管理器為該塊在緩沖區(qū)中分配空間 ， 如果有必要 ，替換緩沖區(qū)中的其他塊 ? 如果被替換的塊被修改過(guò) ， 則將其寫回磁盤 ? 將所需的塊調(diào)入緩沖區(qū) ， 返回其在緩沖區(qū)的地址 緩沖區(qū)管理 ? 被釘住的塊 (pinned blocks) ? 不允許寫回磁盤的塊 ? 當(dāng)一個(gè)塊上的更新正在進(jìn)行時(shí) ， 不允許寫回磁盤 ? 釘住被頻繁訪問(wèn)的小表 ? 塊的強(qiáng)制輸出 (forced output of blocks) ? 先寫日志原則 ? 檢查點(diǎn) ? 提交事務(wù)的日志記錄 緩沖區(qū)管理 ：替換策略 ? LRU(最近最少使用 ) ? 如果必須替換一個(gè)塊 ， 則替換最近最少使用的塊 ? MRU(最近最常使用 ) ? 如果必須替換一個(gè)塊 ， 則替換最近最常使用的塊 SR ??對(duì)于 R中的每條元組 tr 對(duì)于 S中的每條元組 ts …… ? 一旦 R中的一個(gè)元組處理完 ， 就不會(huì)再使用它了 ， 應(yīng)該立即丟棄 (toss immediate) ? 當(dāng) S 中的一個(gè)元組被處理完 ， 只 有 其 他 S中的元組都被處理完后才會(huì)再用到它 ， 應(yīng)該采用 MRU 替換策略 ? 當(dāng)使用者第一次向數(shù)據(jù)庫(kù)發(fā)出查詢數(shù)據(jù)的請(qǐng)求時(shí) ， 數(shù)據(jù)庫(kù)會(huì)先在緩沖區(qū)中查找該數(shù)據(jù) ,如果要訪問(wèn)的數(shù)據(jù)恰好已經(jīng)在緩沖區(qū)中 (稱之為Cache Hit),那么就直接用緩沖區(qū)中讀取該數(shù)據(jù) . ? 反之如果緩沖區(qū)中沒(méi)有使用者要查詢的數(shù)據(jù)稱之為 Cache Miss,這種情況下數(shù)據(jù)庫(kù)就會(huì)先從磁盤上讀取使用者要的數(shù)據(jù)放入緩沖區(qū) ,使用者再?gòu)木彌_區(qū)讀取該數(shù)據(jù) . ? 很顯然 Cache Hit會(huì)比 Cache Miss時(shí)存取速度快 . OPTIMAL/FIFO ? OPTIMAL：最佳置換算法 。 它是由 Belady于 1966年提出的一種理論上的算法 。 其所選擇的被淘汰頁(yè)面 ， 將是以后永不使用的 ， 或是在最長(zhǎng) （ 未來(lái) ） 時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面 。 采用最佳置換算法 ， 通?？杀ＷC獲得最低的缺頁(yè)率 。 但由于人目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中 ， 哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的 ， 因而該算法是無(wú)法實(shí)現(xiàn)的 ，一般可以利用此算法來(lái)評(píng)價(jià)其它算法 。 ? FIFO：先進(jìn)先出置換算法 。 這是最早出現(xiàn)的置換算法 。 該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面 ， 即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰 。 該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面 ， 按先后次序鏈接成一個(gè)隊(duì)列 ， 并設(shè)置一個(gè)指針 ， 稱為替換指針 ， 使它總是指向最老的頁(yè)面 。 例 ? 在一個(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è)開(kāi)始執(zhí)行時(shí)主存中沒(méi)有頁(yè)面 )， 并比較所得結(jié)果 。 ? (1)最佳置換法 (OPT) ? (2)先進(jìn)先出法 (FIFO) 例 ? 最佳頁(yè)面置換算法 :塊為 3：缺頁(yè)次數(shù)為 7 ? 塊為 3：缺頁(yè)次數(shù)為 6 例 例? 先進(jìn)先出頁(yè)面置換算法 :塊為 3：缺頁(yè)次數(shù)為 9 ? 塊為 3：缺頁(yè)次數(shù)為 10 LRU ? LRU算法 (Least recently used)的基本概念是 :當(dāng)內(nèi)存的剩余的可用空間不夠時(shí) ,緩沖區(qū)盡可能的先保留使用者最常使用的數(shù)據(jù) ,就是優(yōu)先清除 ” 較不常使用的數(shù)據(jù) ” ,并釋放其空間 . ? FIFO置換算法性能之所以較差 ， 是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間 ， 而頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況 。 最近最久未使用 （ LRU）置換算法 ， 是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的 。 由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況 ， 只能利用 “ 最近的過(guò)去 ” 作為 “ 最近的將來(lái) ” 的近似 ， 因此 ，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰 。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段 ， 用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間 t,， 當(dāng)須淘汰一個(gè)頁(yè)面時(shí) ， 選擇現(xiàn)有頁(yè)面中其 t值最大的 ， 即最近最久未使用的頁(yè)面予以淘汰 。 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è)面 。 ? 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 7 0 1 2 0 0 0 0 2 3 0 3 2 2 2 0 1 1 0 7 0 1 2 2 2 2 0 2 3 0 3 3 3 2 0 0 1 7 0 1 1 1 4 4 0 2 2 0 0 0 3 2 2 2 7 7 3 3 3 3 4 4 4 4 1 1 1 3 7 7 * * * * * * * * 缺頁(yè)中斷次數(shù)： 8 緩沖區(qū)管理 ： SQL Server ? 訪問(wèn)內(nèi)存頁(yè)面 ? 為快速找到頁(yè)面 ， 內(nèi)存頁(yè)面地址被散列 ? 給定 dbidfilenopageno標(biāo)識(shí) (數(shù)據(jù)庫(kù) ID, 文件號(hào) 、頁(yè)面號(hào)的組合 )， 計(jì)算其 hash地址 ? Lazywriter(緩沖池管理器 ) ? 使用時(shí)鐘算法 時(shí)鐘算法 ? SQL Server 2022使用一個(gè)專門的進(jìn)程 ， 采用時(shí)鐘算法進(jìn)行頁(yè)面置換 。 它為每個(gè)緩沖區(qū)設(shè)置一個(gè)計(jì)數(shù)器 ， 每隔一段時(shí)間則順序掃描緩沖池里的每一個(gè)緩沖區(qū) ， 檢查計(jì)數(shù)器 。 如果計(jì)數(shù)器為零 ， 則說(shuō)明這一緩沖區(qū)可回收使用 。 于是 ， 系統(tǒng)先將緩沖區(qū)內(nèi)臟數(shù)據(jù)寫入磁盤 ， 而后將緩中區(qū)放入自由緩沖區(qū)列表 。如果計(jì)數(shù)器的值不為零 ， 系統(tǒng)則將計(jì)數(shù)器的值減少 。 而當(dāng)某個(gè)進(jìn)程訪問(wèn)緩沖區(qū)的數(shù)據(jù)時(shí) ， 該緩沖區(qū)的計(jì)數(shù)器則會(huì)增加 。 ? 對(duì)于緩沖區(qū)內(nèi)那些通過(guò)較高代價(jià)產(chǎn)生的對(duì)象 ， 系統(tǒng)使用具有較高參考價(jià)值的計(jì)數(shù)器 。 在順序掃描時(shí) ， 這些計(jì)數(shù)器的值不是簡(jiǎn)單的減少 ， 而是以某種策略縮小 （ 如除以 4） ， 這樣可以保證它不會(huì)很快變成零 ， 從而可以在內(nèi)存中貯存較長(zhǎng)時(shí)間 。 ? 其它類似用到緩沖區(qū)的設(shè)計(jì) （ 當(dāng)緩存不足以放下所有數(shù)據(jù)或?yàn)榱斯?jié)省內(nèi)存 ） ， 均可參考此種替換策略 。 索引 ? 順序索引 ? 基于值的順序排序 ? 散列索引 ? 基于將值平均分布到若干散列桶中 ? 索引評(píng)價(jià)指標(biāo) ? 訪問(wèn)類型 ? 訪問(wèn)時(shí)間 ? 插入時(shí)間 ? 刪除時(shí)間 ? 空間開(kāi)銷 主索引和輔助索引 ? 主索引 (primary index)、 輔助索引 (secondary index)；聚集索引 (cluster index)、 非聚集索引(noncluster index) branch_name balance 主索引 ? 主索引包含表中每條記錄的索引關(guān)鍵字并且當(dāng)未指定任何其他索引作為表主索引時(shí)的默認(rèn)索引 。 主索引禁止為產(chǎn)生索引關(guān)鍵字所指定字段或索引表達(dá)式中的重復(fù)值；因此 ， 主索引中每個(gè)索引關(guān)鍵字是唯一的 。 每個(gè)表只能創(chuàng)建一個(gè)主索引 。 ? 注意：主索引是數(shù)據(jù)庫(kù)表的整體部分 。 如果從數(shù)據(jù)庫(kù)中釋放一個(gè)表 ， 則主索引被移去 。 如果在任何包含重復(fù)數(shù)據(jù)的字段上指定主索引 ，將 產(chǎn)生一個(gè)錯(cuò)誤 。 唯一索引 ? 索引還可以用于強(qiáng)迫字段數(shù)值的唯一性 ， 或者是多個(gè)字段組合值的唯一性： CREATE UNIQUE INDEX name ON table (column [, ...])。 目前 ， 只有 Btree 索引可以聲明為唯一的 。 ? 如果索引聲明為唯一的 ， 那么就不允許出現(xiàn)多個(gè)索引值相同的行 。 我們認(rèn)為 NULL 值相互間不相等 。 一個(gè)多字段唯一索引認(rèn)為只有兩行數(shù)據(jù)里所有被索引字段都相同的時(shí)候才是相同的 ， 這種數(shù)據(jù)才被拒絕 。 ? 如果一個(gè)表聲明了一個(gè)唯一約束或者一個(gè)主鍵 ， 那么 SQL 自動(dòng)在那些組成主鍵或者唯一字段的列上創(chuàng)建唯一索引 (可能地話是一個(gè)多字段索引 )， 以強(qiáng)迫這些約束 。 ? 注意 : 給一個(gè)表增加唯一約束的比較好的辦法是 ALTER TABLE ... ADD CONSTRAINT。 我們沒(méi)有必要在唯一字段上建立索引 ， 那樣做只會(huì)重復(fù)建立自動(dòng)創(chuàng)建的索引 。 主索引 VS唯一索引 ? 主索引一定是唯一索引； ? 唯一索引不一定是主索引； ? 主索引只有一個(gè)； ? 唯一索引可有多個(gè) 聚集索引 (Clustered Index) ? 聚集索引規(guī)定數(shù)據(jù)在表中的物理存儲(chǔ)順序：聚集索引表記錄的排列順序與索引的排列順序一致 。 因此一個(gè)表只能包含一個(gè)聚集索引 。 但該索引可以包含多個(gè)列 （ 組合索引 ） 。 ? 聚集索引對(duì)于那些經(jīng)常要搜索范圍值的列特別有效 。 使用聚集索引找到包含第一個(gè)值的行后 ，便可以確保包含后續(xù)索引值的行在物理相鄰 。這樣有助于提高此類查詢的性能 。 同樣 ， 如果對(duì)從表中檢索的數(shù)據(jù)進(jìn)行排序時(shí)經(jīng)常要用到某一列 ， 則可以將該表在該列上聚集 （ 物理排序 ） ， 避免每次查詢?cè)摿袝r(shí)都進(jìn)行排序 ， 從而節(jié)省成本 。 聚集索引 ? 當(dāng)索引值唯一時(shí) ， 使用聚集索引查找特定的行也很有效率 。 例如 ， 使用唯一雇員 ID 列 emp_id 查找特定雇員的最快速的方法 ， 是在 emp_id 列上創(chuàng)建聚集索引或 PRIMARY KEY 約束 。 ? 說(shuō)明 如果該表上尚未創(chuàng)建聚集索引 ， 且在創(chuàng)建 PRIMARY KEY 約束時(shí)未指定非聚集索引 ，PRIMARY KEY 約束會(huì)自動(dòng)創(chuàng)建聚集索引 。 ? 也可以在 lname（ 姓氏 ） 列和 fname（ 名字 ）列上創(chuàng)建聚集索引 ， 因?yàn)楣蛦T記錄常常是按姓名而不是按雇員 ID 分組和查詢的 聚集索引 ? 聚集索引的葉節(jié)點(diǎn)就是實(shí)際的數(shù)據(jù)頁(yè) ? 在數(shù)據(jù)頁(yè)中數(shù)據(jù)按照索引順序存儲(chǔ) ? 行的物理位置和行在索引中的位置是相同的 ? 每個(gè)表只能有一個(gè)聚集索引 ? 聚集索引的平均大小大約為表大小的 5%左右 聚集索引 ? select * from table where firstName = 39。Ota39。 非聚集索引 (Unclustered Index) ? 非聚集索引數(shù)據(jù)存儲(chǔ)在一個(gè)地方 ， 索引存儲(chǔ)在另一個(gè)地方 ， 索引帶有指針指向數(shù)據(jù)的存儲(chǔ)位置 。 索引中的項(xiàng)目按索引鍵值的順序存儲(chǔ) ， 而表中的信息按另一種順序存儲(chǔ) 。 ? SQL Server2022 在搜索數(shù)據(jù)值時(shí) ， 先對(duì)非聚集索引進(jìn)行搜索 ， 找到數(shù)據(jù)值在表中的位置 ， 然后從該位置直接檢索數(shù)據(jù) 。 這使非聚集索引成為精確匹配查詢的最佳方法 ， 因?yàn)樗饕枋霾樵兯阉鞯臄?shù)據(jù)值在表中的精確位置的條目 。 如果基礎(chǔ)表使用聚集索引排序 ， 則該位置為聚集鍵值；否則 ， 該位置為包含行的文件號(hào) 、 頁(yè)號(hào)和槽號(hào)的行 ID (RID)。 例如 ， 對(duì)于在 emp_id 列上有非聚集索引的表 ， 如要搜索其雇員 ID (emp_id)， SQL Server 會(huì)在索引中查找這樣一個(gè)條目 ， 該條目精確列出匹配的 emp_id 列在表