婷婷爱爱网,北条麻妃在线直播,黄色视频日本免费,人妖TS福利视频一二三区,我爱婷婷五月天,青青草原网站在线观看,人人色人人摸人人,日韩无码黄色片

點擊進入【碼農(nóng)編程進階筆記】

免費獲取進階面試題、文檔、視頻資源

問：隨著數(shù)據(jù)庫的增大，既然索引的作用那么重要，有誰能拋開具體的數(shù)據(jù)庫來解釋一下索引的工作原理？

答：

數(shù)據(jù)在磁盤上是以塊的形式存儲的。為確保對磁盤操作的原子性，訪問數(shù)據(jù)的時候會一并訪問所有數(shù)據(jù)塊。磁盤上的這些數(shù)據(jù)塊與鏈表類似，即它們都包含一個數(shù)據(jù)段和一個指針，指針指向下一個節(jié)點（數(shù)據(jù)塊）的內(nèi)存地址，而且它們都不需要連續(xù)存儲（即邏輯上相鄰的數(shù)據(jù)塊在物理上可以相隔很遠）。

鑒于很多記錄只能做到按一個字段排序，所以要查詢某個未經(jīng)排序的字段，就需要使用線性查找，即要訪問N/2個數(shù)據(jù)塊，其中N指的是一個表所涵蓋的所有數(shù)據(jù)塊。如果該字段是非鍵字段（也就是說，不包含唯一值），那么就要搜索整個表空間，即要訪問全部N個數(shù)據(jù)塊。

然而，對于經(jīng)過排序的字段，可以使用二分查找，因此只要訪問log2 N個數(shù)據(jù)塊。同樣，對于已經(jīng)排過序的非鍵字段，只要找到更大的值，也就不用再搜索表中的其他數(shù)據(jù)塊了。這樣一來，性能就會有實質(zhì)性的提升。

什么是索引

索引是對記錄按照多個字段進行排序的一種方式。對表中的某個字段建立索引會創(chuàng)建另一種數(shù)據(jù)結(jié)構(gòu)，其中保存著字段的值，每個值又指向與它相關(guān)的記錄。這種索引的數(shù)據(jù)結(jié)構(gòu)是經(jīng)過排序的，因而可以對其執(zhí)行二分查找。

索引的缺點是占用額外的磁盤空間。因為索引保存在MyISAM數(shù)據(jù)庫中，所以如果為同一個表中的很多字段都建立索引，那這個文件可能會很快膨脹到文件系統(tǒng)規(guī)定的上限。

索引的原理

首先，來看一個示例數(shù)據(jù)庫表的模式：

字段名??????????????數(shù)據(jù)類型?????????在磁盤上的大小
id?(Primary?key)???Unsigned?INT?????4?字節(jié)
firstName??????????Char(50)?????????50?字節(jié)
lastName???????????Char(50)?????????50?字節(jié)
emailAddress???????Char(100)????????100?字節(jié)

注意：這里用char而不用varchar是為了精確地描述數(shù)據(jù)占用磁盤的大小。這個示例數(shù)據(jù)庫中包含500萬行記錄，而且沒有建立索引。接下來我們就分析針對這個表的兩個查詢：一個查詢使用id（經(jīng)過排序的鍵字段），另一個查詢使用firstName（未經(jīng)排序的非鍵字段）。

示例分析一

對于這個擁有r = 5 000 000條記錄的示例數(shù)據(jù)庫，在磁盤上要為每條記錄分配 R = 204字節(jié)的固定存儲空間。這個表保存在MyISAM數(shù)據(jù)庫中，而這個數(shù)據(jù)庫默認的數(shù)據(jù)庫塊大小為 B = 1024字節(jié)。于是，我們可計算出這個表的分塊因數(shù)為 bfr = (B/R) = 1024/204 = 5，即磁盤上每個數(shù)據(jù)塊保存5條記錄。那么，保存整個表所需的數(shù)據(jù)塊數(shù)就是 N = (r/bfr) = 5000000/5 = 1 000 000。

使用線性查找搜索id字段——這個字段是鍵字段（每個字段的值唯一），需要訪問 N/2 ＝ 500 000個數(shù)據(jù)塊才能找到目標值。不過，因為這個字段是經(jīng)過排序的，所以可以使用二分查找法，而這樣平均只需要訪問log2 1000000 = 19.93 = 20 個塊。顯然，這會給性能帶來極大的提升。

再來看看firstName字段，這個字段是未經(jīng)排序的，因此不可能使用二分查找，況且這個字段的值也不是唯一的，所以要從表的開頭查找末尾，即要訪問 N = 1 000 000個數(shù)據(jù)塊。這種情況通過建立索引就能得到改善。

如果一條索引記錄只包含索引字段和一個指向原始記錄的指針，那么這條記錄肯定要比它所指向的包含更多字段的記錄更小。也就是說，索引本身占用的磁盤空間比原來的表更少，因此需要遍歷的數(shù)據(jù)塊數(shù)也比搜索原來的表更少。以下是firstName字段索引的模式：

字段名?????????數(shù)據(jù)類型????????在磁盤上的大小
firstName?????Char(50)????????50?字節(jié)
（記錄指針）????Special?????????4?字節(jié)

注意：在MySQL中，根據(jù)表的大小，指針的大小可能是2、3、4或5字節(jié)。

示例分析二

對于這個擁有r = 5 000 000條記錄的示例數(shù)據(jù)庫，每條索引記錄要占用 R = 54字節(jié)磁盤空間，而且同樣使用默認的數(shù)據(jù)塊大小 B = 1024字節(jié)。那么索引的分塊因數(shù)就是 bfr = (B/R) = 1024/54 = 18。最終這個表的索引需要占用 N = (r/bfr) = 5000000/18 = 277 778個數(shù)據(jù)塊。

現(xiàn)在，再搜索firstName字段就可以使用索引來提高性能了。對索引使用二分查找，需要訪問 log2 277778 = 18.09 = 19個數(shù)據(jù)塊。再加上為找到實際記錄的地址還要訪問一個數(shù)據(jù)塊，總共要訪問 19 + 1 = 20個數(shù)據(jù)塊，這與搜索未索引的表需要訪問277 778個數(shù)據(jù)塊相比，不啻于天壤之別。

什么時候用索引

創(chuàng)建索引要額外占用磁盤空間（比如，上面例子中要額外占用277 778個數(shù)據(jù)塊），建立的索引太多可能導致磁盤空間不足。因此，在建立索引時，一定要慎重選擇正確的字段。

由于索引只能提高搜索記錄中某個匹配字段的速度，因此在執(zhí)行插入和刪除操作的情況下，僅為輸出結(jié)果而為字段建立索引，就純粹是浪費磁盤空間和處理時間了；這種情況下不用建立索引。另外，由于二分查找的原因，數(shù)據(jù)的基數(shù)性（cardinality）或唯一性也非常重要。對基數(shù)性為2的字段建立索引，會將數(shù)據(jù)一分為二，而對基數(shù)性為1000的字段，則同樣會返回大約1000條記錄。在這么低的基數(shù)性下，索引的效率將減低至線性查找的水平，而查詢優(yōu)化器會在基數(shù)性小于記錄數(shù)的30%時放棄索引，實際上等于索引純粹只會浪費空間。

查詢優(yōu)化器的原理：
? ? 查詢優(yōu)化中最核心的問題就是精確估算不同查詢計劃的成本。優(yōu)化器在估算查詢計劃的成本時，會使用一個數(shù)學模型，該模型又依賴于對每個查詢計劃中涉及的最大數(shù)據(jù)量的基數(shù)性（或者叫重數(shù)）的估算。而對基數(shù)性的估算又依賴于對查詢中謂詞選擇因數(shù)（selection factor of predicates）的估算。過去，數(shù)據(jù)庫系統(tǒng)在估算選擇性時，要使用每個字段中值的分布情況的詳盡統(tǒng)計信息，比如直方圖。這種技術(shù)對于估算孤立謂詞的選擇符效果很好。然而，很多查詢的謂詞是相互關(guān)聯(lián)的，例如select count(*) from R where R.make='Honda' and R.model='Accord'。查詢謂詞經(jīng)常會高度關(guān)聯(lián)（比如，model='Accord'的前提條件是make='Honda'），而估計這種關(guān)聯(lián)的選擇性非常困難。查詢優(yōu)化器之所以會選擇低劣的查詢計劃，一方面是因為對基數(shù)性估算不準，另一方面就是因為遺漏了很多關(guān)聯(lián)性。而這也是為什么數(shù)據(jù)庫管理員應該經(jīng)常更新數(shù)據(jù)庫統(tǒng)計信息（特別是在重要的數(shù)據(jù)加載和卸載之后）的原因。

最后

如果這篇文章對您有所幫助，或者有所啟發(fā)的話，幫忙掃描下發(fā)二維碼關(guān)注一下，您的支持是我堅持寫作最大的動力。求一鍵三連：點贊、轉(zhuǎn)發(fā)、在看

你知道數(shù)據(jù)庫索引的工作原理嗎？