先來(lái)看個(gè)問(wèn)題

假設(shè)現(xiàn)在有100000條從0到10000且從大到小排列的整型數(shù)據(jù)，1條數(shù)據(jù)的大小假設(shè)(真的只是假設(shè))是1KB,操作系統(tǒng)的每次I/O數(shù)據(jù)塊(頁(yè))大小是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ù)也不能單單通過(guò)一次I/O全部進(jìn)入內(nèi)存，進(jìn)行運(yùn)算。

那么怎樣在I/O塊大小的限制下快速利用二分查找找到目標(biāo)值呢？我們得引入新的數(shù)據(jù)結(jié)構(gòu)，B+樹(shù)正好可以解決上述I/O塊大小的限制，解決限制不是說(shuō)增大了限制范圍，而是我們在此限制上改變了數(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ū)塊表示的是子樹(shù)的指針域，比如根節(jié)點(diǎn)下的P2指向的就是28-65之間的索引。
2. 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。(而B(niǎo)樹(shù)的葉子節(jié)點(diǎn)并沒(méi)有包括全部需要查找的信息)
3. 所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹(shù)根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵字。(而B(niǎo)樹(shù)的非終節(jié)點(diǎn)也包含需要查找的有效信息)

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

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

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

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

image

概述

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

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

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

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

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

四種索引

• 普通索引

  純粹只是為了查詢(xún)更快，沒(méi)有任何限制

  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è)字段的組合上建立索引，使用組合索引需要遵循最左前綴集合（在查詢(xún)條件中使用這些字段的左邊字段），例如：由id、name和age3個(gè)字段構(gòu)成的索引，索引行中就按id/name/age的順序存放，索引可以索引下面字段組合(id，name，age)、(id，name)或者(id)。如果要查詢(xún)的字段不構(gòu)成索引最左面的前綴，那么就不會(huì)是用索引，比如，age或者（name，age）組合就不會(huì)使用索引查詢(xún)

  創(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類(lèi)型字段上使用全文索引，全文索引就是在一堆文字中，通過(guò)其中的某個(gè)關(guān)鍵字等，就能找到該字段所屬的記錄行，比如有"你在吃飯，它在看電視" 通過(guò)“吃飯”，可能就可以找到該條記錄。

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

  alter table table_name add fulltext ('col_name');
  
  

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

• 空間索引

  空間索引是對(duì)空間數(shù)據(jù)類(lèi)型的字段建立的索引，MySQL中的空間數(shù)據(jù)類(lèi)型有四種，GEOMETRY、POINT、LINESTRING、POLYGON。在創(chuàng)建空間索引時(shí)，使用SPATIAL關(guān)鍵字。要求，引擎為MyISAM，創(chuàng)建空間索引的列，必須將其聲明為NOT NULL?？赡芨螒蜷_(kāi)發(fā)有關(guān)。

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

IndexType.jpg

• Hash索引

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

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

• B+ Tree索引

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

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

  帶順序訪問(wèn)指針——

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

  減少磁盤(pán)I/O讀取——

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

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

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

ps：

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

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

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

image

• 聚簇索引

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

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

• 非聚簇索引

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

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

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

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

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

1. 插入速度嚴(yán)重依賴(lài)于插入順序，按照主鍵的順序插入是最快的方式，否則將會(huì)出現(xiàn)頁(yè)分裂，嚴(yán)重影響性能。因此，對(duì)于InnoDB表，我們一般都會(huì)定義一個(gè)自增的ID列為主鍵（不懂?。。。?。
2. 更新主鍵的代價(jià)很高，因?yàn)閷?huì)導(dǎo)致被更新的行移動(dòng)。因此，對(duì)于InnoDB表，我們一般定義主鍵為不可更新。
3. 二級(jí)索引訪問(wèn)需要兩次索引查找，第一次找到主鍵值，第二次根據(jù)主鍵值找到行數(shù)據(jù)。二級(jí)索引的葉節(jié)點(diǎn)存儲(chǔ)的是主鍵值，而不是行指針（非聚簇索引存儲(chǔ)的是指針或者說(shuō)是地址），這是為了減少當(dāng)出現(xiàn)行移動(dòng)或數(shù)據(jù)頁(yè)分裂時(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ù)行的指針，索引較小，所以比全表掃描快

• 松散掃描

  為了提高緊湊索引掃描效率，通過(guò)把索引排序和查找算法（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ù)定位速度將更快。這種索引掃描方式就稱(chēng)為松散索引掃描。

• 覆蓋掃描

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

一些要注意的

1. 唯一索引與唯一約束

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

   博客中的一句話說(shuō)的很在理，你為了做到數(shù)據(jù)不能有重復(fù)值，但是數(shù)據(jù)庫(kù)怎么保證沒(méi)有重復(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ì)使用索引（在以通配符%和_開(kāi)頭作查詢(xún)時(shí)，MySQL不會(huì)使用索引）

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

索引的代價(jià)

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

在哪些字段上使用索引

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

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

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

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

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

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

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

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

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

• 盡量避免NULL

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

選擇主鍵類(lèi)型

• 整型：通常是作為標(biāo)識(shí)符的最好選擇，因?yàn)榭梢愿斓奶幚?，而且可以設(shè)置為AUTO_INCREMENT。
• 字符串：盡量避免使用字符串作為標(biāo)識(shí)符，它們消耗更好的空間，處理起來(lái)也較慢。而且，通常來(lái)說(shuō)，字符串都是隨機(jī)的，所以它們?cè)谒饕械奈恢靡彩请S機(jī)的，這會(huì)導(dǎo)致頁(yè)面分裂、隨機(jī)訪問(wèn)磁盤(pán)，聚簇索引分裂（對(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)]])