先來看個(gè)問題

假設(shè)現(xiàn)在有100000條從0到10000且從大到小排列的整型數(shù)據(jù)你画，1條數(shù)據(jù)的大小假設(shè)(真的只是假設(shè))是1KB,操作系統(tǒng)的每次I/O數(shù)據(jù)塊(頁)大小是8KB晨汹。如果現(xiàn)在我要查找其中 50001 這個(gè)數(shù)據(jù)值豹储，有如下幾個(gè)方式：

1. 最蠢的方式，遍歷淘这，每次遍歷到一個(gè)值剥扣，就用這個(gè)值跟目標(biāo)值做對(duì)比巩剖，如果不等于那么查找下一個(gè)。這樣的話那么每次I/O是8條數(shù)據(jù)钠怯，目標(biāo)數(shù)據(jù)在50001/8 約6600多次I/O 才能找到目標(biāo)數(shù)據(jù)佳魔。
2. 二分查找，最好一次性將100000條數(shù)據(jù)全部讀到內(nèi)存晦炊，這樣查找也是很快的鞠鲜。

但是即使二分查找很快，但這些數(shù)據(jù)也不能單單通過一次I/O全部進(jìn)入內(nèi)存断国，進(jìn)行運(yùn)算贤姆。

那么怎樣在I/O塊大小的限制下快速利用二分查找找到目標(biāo)值呢？我們得引入新的數(shù)據(jù)結(jié)構(gòu)稳衬，B+樹正好可以解決上述I/O塊大小的限制霞捡，解決限制不是說增大了限制范圍，而是我們在此限制上改變了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)薄疚，即在同等限制條件下碧信，快速檢索到目標(biāo)數(shù)據(jù)，下面講解下B+ Tree

image

上圖中：

1. 圖上藍(lán)色的塊為關(guān)鍵字街夭，我們發(fā)現(xiàn)所有的關(guān)鍵字最終都會(huì)被包含在葉子節(jié)點(diǎn)當(dāng)中音婶。圖上的黃色區(qū)塊表示的是子樹的指針域，比如根節(jié)點(diǎn)下的P2指向的就是28-65之間的索引莱坎。
2. 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針寸士，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接檐什。(而B樹的葉子節(jié)點(diǎn)并沒有包括全部需要查找的信息)
3. 所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最腥蹩ā）關(guān)鍵字乃正。(而B樹的非終節(jié)點(diǎn)也包含需要查找的有效信息)

因此：數(shù)據(jù) 60 的 查找過程如下

1. I/O第一次：讀入5、28婶博、65數(shù)據(jù)塊瓮具，在此同級(jí)別節(jié)點(diǎn)塊上，60在28到65之間(其實(shí)是二分查找)凡人，那走P2指針指向的子樹名党。
2. I/O第二次：讀入28、35挠轴、56數(shù)據(jù)塊传睹，在此同級(jí)別節(jié)點(diǎn)塊上，60大于56岸晦，所以走P3指針指向的子樹(上圖中就是葉子節(jié)點(diǎn))欧啤。
3. I/O第三次：讀入葉子節(jié)點(diǎn)睛藻，在這個(gè)葉子節(jié)點(diǎn)中，使用二分查找算法找到目標(biāo)值60邢隧。

預(yù)備知識(shí)

InnoDB中店印，各個(gè)數(shù)據(jù)頁之間組成一個(gè)雙向鏈表（頁之間未必連續(xù)，所以是鏈表）倒慧，而每個(gè)數(shù)據(jù)頁內(nèi)的記錄又組成一個(gè)單向鏈表按摘，每個(gè)數(shù)據(jù)頁都會(huì)為存儲(chǔ)在它里邊兒的記錄生成一個(gè)頁目錄，在通過主鍵查找某條記錄的時(shí)候可以在頁目錄中使用二分法快速定位到對(duì)應(yīng)的槽迫靖，然后再遍歷該槽對(duì)應(yīng)分組中的記錄即可快速找到指定的記錄院峡。

image

概述

索引是在存儲(chǔ)引擎中實(shí)現(xiàn)的，也就是說不通存儲(chǔ)引擎系宜，會(huì)使用不同的索引照激。

• MyISAM和InnoDB存儲(chǔ)引擎：只支持BTREE索引，也就是說默認(rèn)使用BTREE盹牧，不能夠更換
• MEMORY/HEAP存儲(chǔ)引擎：支持HASH和BTREE索引

索引優(yōu)化也是mysql中的一種優(yōu)化方式俩垃，mysql索引的四種類型：

• 單列索引（普通索引、主鍵索引汰寓、唯一索引——都只對(duì)一個(gè)字段建立索引）
• 組合索引
• 全文索引
• 空間索引（少用）

索引也是一張表口柳，該表保存了主鍵與索引字段，并指向?qū)嶓w表的記錄

四種索引

• 普通索引

  純粹只是為了查詢更快有滑，沒有任何限制

  alter table table_name add index index_name ('字段名')
  

• 主鍵索引

  唯一索引中的一種跃闹，需要指定PRIMARY KEY，一表只有一個(gè)主鍵

  alert table table_name add primary key ('key name');
  
  create table 'student'(
      'stu_id' int(11) not null auto_increment,
      primary key('stu_id')
  )ENGINE=INNODB AUTO_INCREMENT=12 DEFAULT CHARSET=utf8;
  

• 唯一索引

  索引列的值唯一毛好，值可以為空（允許多個(gè)空值）

  create unique index UK_student_name on student(name);
  
  alter table table_name add unique index index_name ('key name');
  
  create table 'student'(
      'stu_id' int(11) not null auto_increment,
      'name' varchar(255) default null,
      primary key('stu_id'),
      unique key 'UK_student_name' ('name')
  )ENGINE=INNODB AUTO_INCREMENT=12 DEFAULT CHARSET=utf8;
  
  建表后添加約束:
  alter table student add constraint uk_student_name unique (name);
  

• 組合索引

  在表中多個(gè)字段的組合上建立索引望艺，使用組合索引需要遵循最左前綴集合（在查詢條件中使用這些字段的左邊字段），例如：由id肌访、name和age3個(gè)字段構(gòu)成的索引找默，索引行中就按id/name/age的順序存放，索引可以索引下面字段組合(id吼驶，name惩激，age)、(id蟹演，name)或者(id)风钻。如果要查詢的字段不構(gòu)成索引最左面的前綴，那么就不會(huì)是用索引酒请，比如魄咕，age或者（name，age）組合就不會(huì)使用索引查詢

  創(chuàng)建組合索引應(yīng)該把最頻繁使用的字段放在最左邊

• 全文索引（前綴索引）

  當(dāng)索引的字符串列很大時(shí)蚌父，創(chuàng)建的索引也就變得很大哮兰，為了減小索引體積毛萌，提高索引的掃描速度，就用索引的前部分字串索引喝滞，這樣索引占用的空間就會(huì)大大減少阁将，并且索引的選擇性也不會(huì)降低很多。而且是對(duì)BLOB和TEXT列進(jìn)行索引右遭，或者非常長(zhǎng)的VARCHAR列做盅，就必須使用前綴索引，因?yàn)镸ySQL不允許索引它們的全部長(zhǎng)度窘哈。

  使用：
  列的前綴的長(zhǎng)度選擇很重要吹榴，又要節(jié)約索引空間，又要保證前綴索引的選擇性要和索引全長(zhǎng)度選擇性接近滚婉。

  MyISAM支持全文索引图筹，InnoDB在mysql5.6之后支持了全文索引，只能在CHAR,VARCHAR,TEXT類型字段上使用全文索引让腹，全文索引就是在一堆文字中远剩，通過其中的某個(gè)關(guān)鍵字等，就能找到該字段所屬的記錄行骇窍，比如有"你在吃飯瓜晤，它在看電視" 通過“吃飯”，可能就可以找到該條記錄腹纳。

  但是可能耗時(shí)間痢掠、耗空間

  alter table table_name add fulltext ('col_name');
  
  

  全文索引并不是和MyISAM一起誕生的，它的出現(xiàn)是為了解決WHERE name LIKE “%word%"這類針對(duì)文本的模糊查詢效率較低的問題嘲恍。

• 空間索引

  空間索引是對(duì)空間數(shù)據(jù)類型的字段建立的索引志群，MySQL中的空間數(shù)據(jù)類型有四種，GEOMETRY蛔钙、POINT、LINESTRING荠医、POLYGON吁脱。在創(chuàng)建空間索引時(shí)，使用SPATIAL關(guān)鍵字彬向。要求兼贡，引擎為MyISAM，創(chuàng)建空間索引的列娃胆，必須將其聲明為NOT NULL遍希。可能跟游戲開發(fā)有關(guān)里烦。

mysql索引的兩種結(jié)構(gòu)

IndexType.jpg

• Hash索引

  MySQL中凿蒜，只有Memory（Memory表只存在內(nèi)存中禁谦，斷電會(huì)消失，適用于臨時(shí)表）存儲(chǔ)引擎顯示支持Hash索引废封，是Memory表的默認(rèn)索引類型州泊，盡管Memory表也可以使用B+Tree索引。hsah索引把數(shù)據(jù)的索引以hash形式組織起來漂洋，因此當(dāng)查找某一條記錄的時(shí)候,速度非骋Ｔ恚快。當(dāng)時(shí)因?yàn)槭莌ash結(jié)構(gòu)刽漂，每個(gè)鍵只對(duì)應(yīng)一個(gè)值演训，而且是散列的方式分布。所以他只在“=”和“in”條件下高效贝咙，并不支持范圍查找和排序等功能

  innodb會(huì)監(jiān)控表上的索引使用情況样悟，如果觀察到建立哈希索引可以帶來速度的提升，那就建立哈希索引颈畸，自 適應(yīng)哈希索引通過緩沖池的B+樹構(gòu)造而來乌奇，因此建立的速度很快，不需要將整個(gè)表都建哈希索引眯娱，InnoDB 存儲(chǔ)引擎會(huì)自動(dòng)根據(jù)訪問的頻率和模式來為某些頁建立哈希索引礁苗。自適應(yīng)哈希索引不需要存儲(chǔ)磁盤

• B+ Tree索引

  MYSQL、PGSQL徙缴、SQL-SERVER-ORACLE都離不開B-TREE索引试伙，HASH索引，B-TREE可以做范圍查找于样，基于葉子節(jié)點(diǎn)的查找適合于WHERE語句疏叨。MYSQL對(duì)WHERE A=XXXX特別做了優(yōu)化，使用了HASH索引穿剖，HASH索引則適合于隨機(jī)查找蚤蔓，無法或需要做SCAN時(shí)需要其他的方式。

  B+tree是mysql使用最頻繁的一個(gè)索引數(shù)據(jù)結(jié)構(gòu)糊余，是Inodb和Myisam存儲(chǔ)引擎模式的索引類型秀又。相對(duì)Hash索引，B+樹在查找單條記錄的速度比不上Hash索引贬芥，但是因?yàn)楦m合排序等操作吐辙，所以他更受用戶的歡迎。畢竟不可能只對(duì)數(shù)據(jù)庫進(jìn)行單條記錄的操作蘸劈。

  帶順序訪問指針——

  B+Tree所有索引數(shù)據(jù)都在葉子結(jié)點(diǎn)上昏苏，并且增加了順序訪問指針,每個(gè)葉子節(jié)點(diǎn)都有指向相鄰葉子節(jié)點(diǎn)的指針。這樣做是為了提高區(qū)間查詢效率，例如查詢key為從18到49的所有數(shù)據(jù)記錄贤惯，當(dāng)找到18后洼专，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢效率救巷。

  減少磁盤I/O讀取——

  用了磁盤預(yù)讀原理壶熏，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入浦译。

  實(shí)際實(shí)現(xiàn)B- Tree還需要使用如下技巧：每次新建節(jié)點(diǎn)時(shí)棒假，直接申請(qǐng)一個(gè)頁的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁里精盅，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁對(duì)齊的帽哑，就實(shí)現(xiàn)了一個(gè)node只需一次I/O。

  B+ Tree根節(jié)點(diǎn)常駐內(nèi)存

ps：

• 索引合并叹俏，使用多個(gè)單列索引組合搜索
• 覆蓋索引妻枕，select的數(shù)據(jù)列只用從索引中就能夠取得，不必讀取數(shù)據(jù)行粘驰，換句話說查詢列要被所建的索引覆蓋

另一種分類方式（另一篇文章細(xì)講）

InnoDB主鍵使用的是聚簇索引屡谐，MyISAM不管是主鍵索引，還是二級(jí)索引使用的都是非聚簇索引蝌数。

image

• 聚簇索引

  對(duì)于聚簇索引表來說（左圖）愕掏，表數(shù)據(jù)是和主鍵一起存儲(chǔ)的，主鍵索引的葉結(jié)點(diǎn)存儲(chǔ)行數(shù)據(jù)(包含了主鍵值)顶伞，二級(jí)索引的葉結(jié)點(diǎn)存儲(chǔ)行的主鍵值饵撑。使用的是B+樹作為索引的存儲(chǔ)結(jié)構(gòu)，非葉子節(jié)點(diǎn)存儲(chǔ)索引關(guān)鍵字+頁地址（可能有幾層唆貌，因此需要存儲(chǔ)往下面走的頁的地址）滑潘，葉子節(jié)點(diǎn)上的數(shù)據(jù)是主鍵與具體記錄(數(shù)據(jù)內(nèi)容)。

  要注意的是锨咙，在InnoDB中语卤，由于在葉子節(jié)點(diǎn)也就是包含記錄的頁上，頁內(nèi)包含的記錄也會(huì)按照索引列排序酪刀，這樣是方便在頁內(nèi)可以進(jìn)行二分查找粹舵；與此同時(shí)，帶來的壞處是蓖宦，如果此頁已滿，此時(shí)插入數(shù)據(jù)油猫，可能導(dǎo)致需要分頁的情況發(fā)生

• 非聚簇索引

  對(duì)于非聚簇索引表來說（右圖）稠茂，表數(shù)據(jù)和索引是分成兩部分存儲(chǔ)的，主鍵索引和二級(jí)索引存儲(chǔ)上沒有任何區(qū)別。使用的是B+樹作為索引的存儲(chǔ)結(jié)構(gòu)睬关，所有的節(jié)點(diǎn)都是索引诱担，葉子節(jié)點(diǎn)存儲(chǔ)的是索引+索引對(duì)應(yīng)的記錄的地址（類似指針）。

  非聚簇索引的頁是按照時(shí)間順序插入記錄电爹！也就是說一頁里的內(nèi)容是無序的

聚簇索引的優(yōu)點(diǎn):

1. 當(dāng)你需要取出一定范圍內(nèi)的數(shù)據(jù)時(shí)蔫仙，用聚簇索引也比用非聚簇索引好。
2. 當(dāng)通過聚簇索引查找目標(biāo)數(shù)據(jù)時(shí)理論上比非聚簇索引要快丐箩，因?yàn)?strong>非聚簇索引定位到對(duì)應(yīng)主鍵時(shí)還要多一次目標(biāo)記錄尋址,即多一次I/O摇邦。

聚簇索引的缺點(diǎn):

1. 插入速度嚴(yán)重依賴于插入順序，按照主鍵的順序插入是最快的方式屎勘，否則將會(huì)出現(xiàn)頁分裂施籍，嚴(yán)重影響性能。因此概漱，對(duì)于InnoDB表丑慎，我們一般都會(huì)定義一個(gè)自增的ID列為主鍵（不懂！Ｈ看荨８土选）。
2. 更新主鍵的代價(jià)很高照弥，因?yàn)閷?huì)導(dǎo)致被更新的行移動(dòng)腻异。因此，對(duì)于InnoDB表产喉，我們一般定義主鍵為不可更新捂掰。
3. 二級(jí)索引訪問需要兩次索引查找，第一次找到主鍵值曾沈，第二次根據(jù)主鍵值找到行數(shù)據(jù)这嚣。二級(jí)索引的葉節(jié)點(diǎn)存儲(chǔ)的是主鍵值，而不是行指針（非聚簇索引存儲(chǔ)的是指針或者說是地址）塞俱，這是為了減少當(dāng)出現(xiàn)行移動(dòng)或數(shù)據(jù)頁分裂時(shí)二級(jí)索引的維護(hù)工作姐帚，但會(huì)讓二級(jí)索引占用更多的空間。
4. 采用聚簇索引插入新值比采用非聚簇索引插入新值的速度要慢很多障涯，因?yàn)椴迦胍ＷC主鍵不能重復(fù)罐旗，判斷主鍵不能重復(fù)，采用的方式在不同的索引下面會(huì)有很大的性能差距唯蝶，聚簇索引遍歷所有的葉子節(jié)點(diǎn)九秀，非聚簇索引也判斷所有的葉子節(jié)點(diǎn)，但是聚簇索引的葉子節(jié)點(diǎn)除了帶有主鍵還有記錄值粘我，記錄的大小往往比主鍵要大的多鼓蜒。這樣就會(huì)導(dǎo)致聚簇索引在判定新記錄攜帶的主鍵是否重復(fù)時(shí)進(jìn)行昂貴的I/O代價(jià)痹换。

索引的掃描方式

• 緊湊掃描

  數(shù)據(jù)與索引不是放在一塊的，索引中存放了指向?qū)?yīng)數(shù)據(jù)行的指針都弹，索引較小娇豫，所以比全表掃描快

• 松散掃描

  為了提高緊湊索引掃描效率，通過把索引排序和查找算法（B+trre）畅厢，發(fā)現(xiàn)只需要和每個(gè)數(shù)據(jù)塊的第一行鍵值匹配冯痢，就可以判斷下一個(gè)數(shù)據(jù)塊的位置或方向，因此有效數(shù)據(jù)就是每個(gè)數(shù)據(jù)塊的第一行數(shù)據(jù)框杜，如果把每個(gè)數(shù)據(jù)塊的第一行數(shù)據(jù)創(chuàng)建索引浦楣，這樣在這個(gè)新創(chuàng)建的索引上折半查找，數(shù)據(jù)定位速度將更快霸琴。這種索引掃描方式就稱為松散索引掃描椒振。

• 覆蓋掃描

  包含所有滿足查詢需要的數(shù)據(jù)的索引稱為覆蓋索引，即利用索引返回select列表中的字段梧乘，而不必根據(jù)索引再次讀取數(shù)據(jù)文件

一些要注意的

1. 唯一索引與唯一約束

   mysql中貌似唯一約束就是唯一索引澎迎，并沒有什么不同，可能叫法不同选调，在sqlserver中區(qū)分還是挺明確的夹供。

   博客中的一句話說的很在理，你為了做到數(shù)據(jù)不能有重復(fù)值仁堪，但是數(shù)據(jù)庫怎么保證沒有重復(fù)值呢哮洽？當(dāng)然是在存儲(chǔ)數(shù)據(jù)的時(shí)候查一遍，那么怎樣查找快呢弦聂？ 當(dāng)然是創(chuàng)建索引鸟辅，所以，在創(chuàng)建唯一約束的時(shí)候就創(chuàng)建了唯一索引莺葫。這可能也是mysql的一個(gè)優(yōu)化機(jī)制

2. MySQL只對(duì)<匪凉，<=，=捺檬，>再层，>=（!=不走索引），BETWEEN堡纬，IN聂受，以及某些時(shí)候的LIKE才會(huì)使用索引（在以通配符%和_開頭作查詢時(shí)，MySQL不會(huì)使用索引）

3. 添加索引的時(shí)候烤镐，可以不寫index

索引的代價(jià)

1. 空間耗費(fèi)
2. 在使用DML語言對(duì)表格進(jìn)行修改的時(shí)候蛋济，同時(shí)需要修改索引，降低效率
3. 如果該字段沒有限制非空的話炮叶，存在插入NULL值的情況碗旅，此時(shí)鹊杖，唯一索引并不起作用，也就是你可以插入n條該字段為null的數(shù)據(jù)扛芽。
4. 如果插入空字符串的話， 例如 ‘’ 积瞒、‘ ’
   不管中間是多少個(gè)空字符串在插入的時(shí)候都算作‘’川尖，即，空串不論多長(zhǎng)茫孔，只能插入一條叮喳。

在哪些字段上使用索引

• 頻繁作為查詢條件者
• 字段值更新不會(huì)太頻繁者
• 字段值不會(huì)僅僅在幾個(gè)確定的值上進(jìn)行選擇

選擇索引的數(shù)據(jù)類型

MySQL支持很多數(shù)據(jù)類型，選擇數(shù)據(jù)類型建立索引遵循一些規(guī)則：

• 越小的數(shù)據(jù)類型

  越小的數(shù)據(jù)類型通常在磁盤缰贝、內(nèi)存和CPU緩存中都需要更少的空間馍悟，處理起來更快

• 簡(jiǎn)單的數(shù)據(jù)類型

  整型數(shù)據(jù)比起字符，處理開銷更小剩晴，因?yàn)樽址谋容^更復(fù)雜锣咒。

  在MySQL中，應(yīng)該用內(nèi)置的日期和時(shí)間數(shù)據(jù)類型赞弥，而不是用字符串來存儲(chǔ)時(shí)間毅整；

  用整型數(shù)據(jù)類型存儲(chǔ)IP地址

• 盡量避免NULL

  含有空值的列很難進(jìn)行查詢優(yōu)化，因?yàn)樗鼈兪沟盟饕雷蟆⑺饕慕y(tǒng)計(jì)信息以及比較運(yùn)算更加復(fù)雜悼嫉。你應(yīng)該用0、一個(gè)特殊的值或者一個(gè)空串代替空值

選擇主鍵類型

• 整型：通常是作為標(biāo)識(shí)符的最好選擇拼窥，因?yàn)榭梢愿斓奶幚硐访铮铱梢栽O(shè)置為AUTO_INCREMENT。
• 字符串：盡量避免使用字符串作為標(biāo)識(shí)符鲁纠，它們消耗更好的空間总棵，處理起來也較慢。而且房交，通常來說彻舰，字符串都是隨機(jī)的，所以它們?cè)谒饕械奈恢靡彩请S機(jī)的候味，這會(huì)導(dǎo)致頁面分裂刃唤、隨機(jī)訪問磁盤，聚簇索引分裂（對(duì)于使用聚簇索引的存儲(chǔ)引擎）白群。

索引的操作

查看

show index from 'table_name';

刪除

alter table 'table_name' drop index 'index_name';

drop index index_name on table_name;

添加主鍵索引：指定主鍵即可

添加唯一索引尚胞、普通索引、復(fù)合索引帜慢、復(fù)合前綴索引（也可以復(fù)合單列索引笼裳，只要后面添加數(shù)字即可）

alter table 'table_name' add index index_name (column_name[, column_name[, column_name(10)]])