哈嘍大家好!我是小三。今天我們來講索引。

索引是什么?

「索引的概念」：索引是一種特殊的文件(InnoDB數(shù)據(jù)表上的索引是表空間的一個(gè)組成部分)，它們包含著對(duì)數(shù)據(jù)表里的所有記錄的引用指針。通俗來說就是數(shù)據(jù)庫索引就好像是一本書的目錄，能夠加快數(shù)據(jù)庫的查詢速度。

「索引的作用」：索引存在的目的就是在于提高查詢效率，使得原始的隨機(jī)全表掃描變成了快速順序鎖定數(shù)據(jù)

常用的索引分類：

1、普通索引：這是最基本的索引，沒有任何的限制

2、唯一索引：引列的值必須唯一，但允許有空值(注意和主鍵不同)

3、組合索引：多個(gè)數(shù)據(jù)列組成的索引，遵守了最左匹配原則

索引高性能保證：

1、把查詢過程中的隨機(jī)事件變成了順序事件

2、數(shù)據(jù)保存在磁盤上，而為了提高性能，每次又可以把一部分的數(shù)據(jù)讀入內(nèi)存來計(jì)算，訪問磁盤的成本大概是訪問內(nèi)存的十萬倍左右。

3、考慮到磁盤IO是非常高昂的操作，計(jì)算機(jī)操作系統(tǒng)做了一系列的優(yōu)化，當(dāng)進(jìn)行一次IO時(shí)，不光把當(dāng)前磁盤的地址的數(shù)據(jù)也把相鄰的數(shù)據(jù)也都讀取到內(nèi)存的緩沖區(qū)之內(nèi)。因?yàn)榫植康念A(yù)讀性原理告訴了我們，當(dāng)計(jì)算機(jī)訪問一個(gè)地址的數(shù)據(jù)的時(shí)候，與它響鈴的數(shù)據(jù)也會(huì)很快被訪問到。每一次IO讀取的數(shù)據(jù)我們都稱之為一頁(page)。具體一頁會(huì)有多大的數(shù)據(jù)，這跟操作系統(tǒng)有關(guān)，一般為4k或者是8k。

那為什么磁盤讀取數(shù)據(jù)會(huì)很慢呢?

我們知道磁盤讀取時(shí)間=尋道時(shí)間+旋轉(zhuǎn)時(shí)間+傳輸時(shí)間，當(dāng)需要從磁盤讀取到數(shù)據(jù)的時(shí)候，系統(tǒng)會(huì)將數(shù)據(jù)的邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成了物理地址，就確定了要讀的數(shù)據(jù) 在哪一個(gè)磁道，哪個(gè)扇區(qū)。為了讀取扇區(qū)的數(shù)據(jù)，需要將磁頭放到扇區(qū)的上方，為了實(shí)現(xiàn)這一點(diǎn)，磁頭需要移動(dòng)對(duì)準(zhǔn)相應(yīng)的磁道，這個(gè)過程叫尋道，在這里所耗費(fèi)的時(shí)間叫做尋道時(shí)間，然后磁盤旋轉(zhuǎn)目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個(gè)過程耗費(fèi)的時(shí)間叫做旋轉(zhuǎn)時(shí)間。

索引的底層實(shí)現(xiàn)方案

我們使用索引的目的，自然是要提高查詢的效率。例如像字典，如果要查詢"mysql"這個(gè)單詞，我們首先肯定是要定位到m字母，然后從下往下找到y(tǒng)字母，以此類推。

索引的設(shè)計(jì)難度

查詢要求：等值查詢，還有范圍查詢(>、<、between、in)、模糊查詢(like)、并集查詢(or)

數(shù)據(jù)量：超過一千萬數(shù)據(jù)通過索引查詢，查詢性能保證

常見的檢索方案分析

順序檢索：最基本的查詢算法-復(fù)雜度O(n)，數(shù)據(jù)量大的話這個(gè)算法的效率是糟糕的

二叉樹查找：O(log2n)，單層節(jié)點(diǎn)所能存儲(chǔ)數(shù)據(jù)量較少，需要進(jìn)行遍歷多層才能拿到數(shù)據(jù)，總結(jié)點(diǎn)數(shù)k與高度h的關(guān)系為k=(2^h)-1

hash索引：無法滿足范圍查找，但是它的等值檢索快，hash值==》物理地址x018，范圍檢索

B-Tree:每個(gè)節(jié)點(diǎn)都是一個(gè)二元數(shù)組：[key,data]，所有的節(jié)點(diǎn)都可以存儲(chǔ)數(shù)據(jù)，key為索引key，data為除之外的數(shù)據(jù)

B+Tree數(shù)據(jù)結(jié)構(gòu)高性能解析

B-Tree的缺點(diǎn)：插入刪除新的數(shù)據(jù)記錄會(huì)破壞掉B-Tree的性質(zhì)，因此在插入刪除時(shí)，需要對(duì)樹進(jìn)行一個(gè)分裂、合并、轉(zhuǎn)移等操作來保持B-Tree的性質(zhì)。在區(qū)間查找時(shí)可能需要返回上層節(jié)點(diǎn)重新，IO操作繁瑣。

B+Tree的改進(jìn)：非葉子節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)了索引的key，只有葉子節(jié)點(diǎn)才存儲(chǔ)data

「高性能的保證」：

第一、3層的b+樹可以表示上百萬的數(shù)據(jù)，如果上百萬的數(shù)據(jù)查找只需要進(jìn)行三次IO的話，那么對(duì)性能的提高無疑是巨大的，如果沒有索引的話，每個(gè)數(shù)據(jù)項(xiàng)都要發(fā)生一次IO那么就會(huì)有百萬次的IO，這顯然成本非常非常高。

第二、在B+Tree的每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰子節(jié)點(diǎn)的指針，這樣就形成了帶有順序訪問指針的B+Tree

第三、B+Tree只在葉子節(jié)點(diǎn)來存儲(chǔ)數(shù)據(jù)，所有的葉子節(jié)點(diǎn)包含一個(gè)鏈指針，其他內(nèi)存的非葉子節(jié)點(diǎn)只存儲(chǔ)索引數(shù)據(jù)。只利用索引快速的定位數(shù)據(jù)索引范圍，先定位索引再通過索引高效的定位數(shù)據(jù)。

mysql為什么會(huì)選錯(cuò)索引

優(yōu)化器的邏輯

Mysql Server層的優(yōu)化器負(fù)責(zé)的是選擇索引，而優(yōu)化器選擇索引的目的就是要找到一個(gè)最優(yōu)的執(zhí)行方案，并且用最小代價(jià)來執(zhí)行語句。在數(shù)據(jù)庫里面，掃描行數(shù)是影響執(zhí)行代價(jià)的因素之一。掃描的行數(shù)越少，也就意味著訪問的磁盤的數(shù)據(jù)次數(shù)就越小，消耗的CPU就越少。掃描行數(shù)并不是唯一的判斷標(biāo)準(zhǔn)，優(yōu)化器還會(huì)結(jié)合了是否使用臨時(shí)表、是否排序等等因素來綜合判斷。

掃描行數(shù)是怎么判斷的

Mysql在真正開始執(zhí)行語句之前，并不可以精確的知道滿足該查詢條件的記錄究竟有多少條，只能根據(jù)統(tǒng)計(jì)的信息來估算記錄數(shù)。所以這個(gè)統(tǒng)計(jì)信息就是索引的“區(qū)分度”。顯然，一個(gè)索引上面的值不同得越多，這個(gè)索引的區(qū)分度就越好。在一個(gè)索引上不同值的個(gè)數(shù)，稱為基數(shù)。

那么，mysql是怎么樣得到索引基數(shù)的?在這里mysql采樣統(tǒng)計(jì)方法，但是為什么要使用采樣統(tǒng)計(jì)這種方法呢?原因就是因?yàn)槿绻颜麖埍砣〕鰜砣缓筮M(jìn)行一行行的統(tǒng)計(jì)，雖然這樣能夠得到精確的數(shù)據(jù)，但是代價(jià)也太高了，所以的話只能使用采樣統(tǒng)計(jì)。

#創(chuàng)建表 
CREATE TABLE `test` ( 
  `id` int(11) NOT NULL, 
  `a` int(11) NOT NULL default 0, 
  `b` int(11) NOT NULL default 0, 
  PRIMARY KEY (`id`), 
  KEY `a` (`a`), 
  KEY `b` (`b`) 
) ENGINE=InnoDB; 
 
#添加數(shù)據(jù) 
delimiter ;; 
create procedure xddata() 
begin 
  declare i int; 
  set i=1; 
  while(i<=100000)do 
    insert into test values(i, i, i); 
    set i=i+1; 
  end while; 
end;; 
delimiter ; 
call xddata(); 
 
數(shù)據(jù)查詢 
explain select * from test where (a between 1000 and 2000) and (b between 50000 and 100000) order by b limit 1; 

「為什么會(huì)出現(xiàn)這種結(jié)果呢?」

在多個(gè)的索引情況下，優(yōu)化器一般會(huì)通過比較了掃描行數(shù)、是否需要臨時(shí)表以及是否需要排序等因素來作為索引的半段依據(jù)。

選擇了索引b，則就需要在b索引上掃描9W條記錄，然后回到主鍵索引上過濾掉不滿足a條件的記錄，因?yàn)樗饕行?，所以使用b索引不需要額外排序。

「解決方案」

使用force index a讓mysql直接選擇a索引來處理此處的查詢

select * from test where (a between 1000 and 2000) and (b between 50000 and 100000) order by b limit 1; 
 
select * from test force index(a) where (a between 1000 and 2000) and (b between 50000 and 100000) order by b limit 1; 

在其他的場(chǎng)景：

數(shù)據(jù)表有頻繁的刪除或者是更新操作導(dǎo)致的數(shù)據(jù)空洞造成的，造成的原因可能是分析器explain的結(jié)果預(yù)估的rows值跟實(shí)際的情況差距比較大，分析器分析掃描行數(shù)用的是抽樣調(diào)查。統(tǒng)計(jì)分析不對(duì)話可以使用analyze table test命令，用來重新統(tǒng)計(jì)索引信息。

【面試題】唯一索引和普通索引的區(qū)別在哪?

「1.查詢上的區(qū)別」

對(duì)唯一索引，由于索引定義了唯一性，查到第一個(gè)滿足條件的記錄之后，就會(huì)停止檢索。

對(duì)普通索引，查找到滿足條件的第一個(gè)記錄'ab'后，需要找下個(gè)記錄，直到碰到第一個(gè)不滿足k='ab'條件的記錄

「2.修改上的區(qū)別」

對(duì)于唯一索引，所有更新操作要先判斷該操作是否會(huì)違反唯一性約束，唯一索引不會(huì)用change buff，若所修改的數(shù)據(jù)在內(nèi)存當(dāng)中，找到索引所對(duì)應(yīng)的存儲(chǔ)位置、判斷到?jīng)]有沖突，然后再插入值，語句執(zhí)行結(jié)束。若所修改的數(shù)據(jù)不在內(nèi)存當(dāng)中，則需要將數(shù)據(jù)頁也讀入內(nèi)存，判斷到?jīng)]有沖突，再插入值，語句執(zhí)行結(jié)束。

「3.性能上的區(qū)別」

普通索引查找數(shù)據(jù)的時(shí)候會(huì)將符合條件的都給查找出來

唯一索引主要是第一條符合條件的就會(huì)立即返回，不會(huì)在繼續(xù)查找了，因?yàn)槲ㄒ坏臑閿?shù)已經(jīng)確保了只有一條符合條件