什么是索引

• 如果沒有索引,掃描的記錄數(shù)大于有索引的記錄數(shù)

• 索引存放索引列的值(好比id為索引列,那么存放索引列的值),和該索引值對(duì)應(yīng)的行在內(nèi)存中的地址(或者直接存儲(chǔ)該行的數(shù)據(jù))

• SELECT * FROM user WHERE username= 'jiajun' ,username建立索引,如果索引采用的數(shù)據(jù)結(jié)構(gòu)是hash表,那么這個(gè)時(shí)候,通過計(jì)算jiajun的hash值,O(1)復(fù)雜度就可以找到該記錄的位置

hash索引

• 在等值查找下,此時(shí)無hash沖突,這種情況下,效率是很高的

• 但是在范圍查找下,由于hash不是有序的,那么范圍查找下,hash表的優(yōu)勢并不能發(fā)揮出來.

• 在hash沖突下,查找效率會(huì)降下來

磁盤讀取

• 磁盤讀取步驟：定柱面,定磁道,定磁塊

• 磁盤時(shí)間主要消耗在定位柱面,那么如果要提高速度,在數(shù)據(jù)量一樣的情況下,將盡量多的數(shù)據(jù)放在磁盤塊上,那么這樣可以減少磁頭定位柱面移動(dòng)的次數(shù),減少IO的次數(shù).

二叉查找樹

• 左子樹所有的節(jié)點(diǎn)的值小于他的根節(jié)點(diǎn)的值

• 右子樹所有的節(jié)點(diǎn)的值大于他的根節(jié)點(diǎn)的值

• 任意節(jié)點(diǎn)的左子樹和右子樹都是二叉查找樹

• 沒有鍵值相等的節(jié)點(diǎn)

分析

• 二叉查找樹的查找的復(fù)雜度到了lgn

• 但是有沒有方法減少IO的次數(shù),也就是能不能降低樹的高度

B-樹

(m階樹 m/2<=k<=m)

• 根節(jié)點(diǎn)至少兩個(gè)子節(jié)點(diǎn)

• 所有葉子節(jié)點(diǎn)都在同一層

• 中間節(jié)點(diǎn)包括k-1個(gè)元素和k個(gè)孩子

• 節(jié)點(diǎn)中的元素從小到大排列

• 每個(gè)節(jié)點(diǎn)即包括索引列的值,和該數(shù)據(jù)記錄(或該數(shù)據(jù)記錄的值)

分析

• 相對(duì)于二叉查找樹,B樹變得矮胖,因?yàn)槊總€(gè)節(jié)點(diǎn)存放的元素更多,所以相同元素情況下,降低了樹的高度,那么就可以減少IO的次數(shù)

• 每個(gè)節(jié)點(diǎn)存放了數(shù)據(jù)(該行記錄的值或者該行記錄在內(nèi)存的地址),所以不同的查詢性能是不一樣的.

B+樹

• 在B-樹的基礎(chǔ)上

• 除了葉子結(jié)點(diǎn),其他節(jié)點(diǎn)不包括記錄(數(shù)據(jù)庫中的行)的位置

• 葉子節(jié)點(diǎn)包括了所有的索引值,并且從小到大排列,以及記錄(數(shù)據(jù)庫中行)的位置

分析

• 如果節(jié)點(diǎn)的大小一樣,那么如果我們除了葉節(jié)點(diǎn)之外,其他節(jié)點(diǎn)不包括數(shù)據(jù),那么就可以放更多的元素(索引值),這樣的話這棵樹就變的更加矮胖,那么IO的次數(shù)可以進(jìn)一步減少

• 因?yàn)槿~節(jié)點(diǎn)的元素是順序排列,而且葉節(jié)點(diǎn)間形成鏈表,那么有序查找時(shí)提高范圍查詢的效率

• 相對(duì)于B樹,由于所有的數(shù)據(jù)是存放在葉節(jié)點(diǎn),那么意味著每次查找都必需到從根查找到葉節(jié)點(diǎn),那么這就意味著查詢性能平均.

總結(jié)

• 索引是一種數(shù)據(jù),可以避免了全表查詢,可以類比目錄和書.

• 索引必要一種數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)

• 利用散列表(hash)的方式查詢復(fù)雜度可以到O(1),但是再范圍查詢時(shí),hash起不了提高性能的作用

• IO操作是耗時(shí),為了提高查詢性能,可以減少IO的次數(shù)

• 對(duì)于樹的存儲(chǔ)結(jié)構(gòu)來說,為了提高性能,減少IO的次數(shù),可以低樹的高度

• 讀取一個(gè)節(jié)點(diǎn)一次IO,在數(shù)據(jù)量一樣的情況下,如果每個(gè)節(jié)點(diǎn)的能存放更多元素,那么就可以降低樹的高度.

• B樹降低了樹的高度,而在節(jié)點(diǎn)大小一樣的情況下,因?yàn)锽樹的節(jié)點(diǎn)存放了元素有又存放了數(shù)據(jù),而B+樹將數(shù)據(jù)全部存放在葉節(jié)點(diǎn),那么這樣的話,每個(gè)節(jié)點(diǎn)可以存放更多的元素,那么就可以再一次降低樹的高度

• B+樹的查詢性能更加穩(wěn)定,并且更有利于范圍查找

• 如果是聚集索引(InnoDB引擎),那么節(jié)點(diǎn)存放的該記錄的數(shù)據(jù),數(shù)據(jù)文件自己就是索引文件

• 如果是非聚集索引(MyISAM引擎),那么節(jié)點(diǎn)存放的是該行記錄的地址.索引文件和數(shù)據(jù)文件是分離

索引的種類

• 普通索引,允許出現(xiàn)相同的內(nèi)容

• 唯一索引,索引值唯一,允許空值

• 主鍵索引,創(chuàng)建主鍵的時(shí)候自動(dòng)創(chuàng)建主鍵索引,唯一并且不能為空

• 組合索引,多列組合索引

聚集索引和非聚集索引

• 聚集索引指的是索引和數(shù)據(jù)文件在一起,在InnoDB引擎中,數(shù)據(jù)文件自己就是索引文件,這個(gè)索引的key是主鍵.InnoDB必須要主鍵,如果沒有顯式指定,則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵,如果不存在這種列,則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵,這個(gè)字段長度為6個(gè)字節(jié),類型為長整形.

• 非聚集索引指的是索引文件和數(shù)據(jù)文件分開.在MyISAM中,B+樹中葉節(jié)點(diǎn)存放的記錄的地址.而在InnoDB中,非主鍵索引的B+樹中存放的是該記錄主鍵值.

索引的使用

• ALTER TABLE table_name ADD INDEX index_name (column_list) 增加普通索引

• ALTER TABLE table_name ADD UNIQUE (column_list) 增加唯一索引

• ALTER TABLE table_name ADD PRIMARY KEY (column_list) 增加主鍵索引

注意點(diǎn)

• 如果此時(shí)為 username,age,sex建聯(lián)合索引

• 最左匹配指優(yōu)先匹配最左索引,(username)(username,age)(username,age,sex),只要查詢條件用到最左邊的列,一般就會(huì)使用索引.順序可以不同,好比(age,username),這是查詢優(yōu)化器的功勞.

• 模糊查詢只有%號(hào)不在第一個(gè)字符,索引才可能被使用,好比username like '%jiajun'所以不被采用

• 如果or中有一個(gè)條件沒有索引,sql語句不會(huì)用到索引,好比usernmae ='jiajun' or pwd='666',此時(shí)索引不被采用

• 組合索引中,如果查詢條件不是索引的第一列,索引可能不會(huì)被采用,好比此時(shí)where age =1

• 如果列是字符型,好比username是字符型而且是索引列,如果此是查詢username=1 ,沒有加引號(hào),那么這個(gè)時(shí)候也不會(huì)用索引

• 可以用 show status like 'Handler_read%' 來查看索引使用情況.

• 建議實(shí)踐為主

索引原則

• 索引應(yīng)該設(shè)計(jì)在where后的列,而不是select后的列

• 索引應(yīng)該建在區(qū)分度大的列,好比狀態(tài)只有1 和2就沒必要建索引了

• 對(duì)字符串進(jìn)行索引的時(shí)候,應(yīng)該制定一個(gè)前綴長度,好比一個(gè)列為char(200),如果前面幾個(gè)字符就要較大區(qū)分度,那么對(duì)前幾個(gè)字符建立索引就行了,這樣減少了占用空間,也提高了速度

• 不要?jiǎng)?chuàng)建太多索引,索引會(huì)占空間,而且更新的時(shí)候會(huì)降低速度,并且如果有過多的索引,Mysql執(zhí)行計(jì)劃的時(shí)候,會(huì)考慮各個(gè)索引,這也會(huì)浪費(fèi)時(shí)間

索引優(yōu)缺點(diǎn)

• 毫無疑問,在使用正確的情況下,索引能提高查詢速度

• 索引也能提高分組和排序的速度

• 由于修改刪除添加時(shí),要調(diào)維護(hù)索引文件,對(duì)樹進(jìn)行調(diào)整,所以性能降低了

• 索引文件也是必要占用空間的