參考：https://blog.csdn.net/tongdanping/article/details/79878302
參考：http://www.cnblogs.com/vianzhang/p/7922426.html （感覺對BTree和B+Tree分析的好透徹，Orz了）
創(chuàng)建索引
創(chuàng)建表的時候添加索引
CREATE TABLE mytable(
ID INT NOT NULL,
username VARCHAR(16) NOT NULL,
INDEX [indexName] (username(length))
);
創(chuàng)建表以后添加索引
ALTER TABLE my_table ADD [UNIQUE] INDEX index_name(column_name);
CREATE INDEX index_name ON my_table(column_name);
根據(jù)索引查詢
具體查詢：
SELECT * FROM table_name WHERE column_1='xxx';(為column_1建立了索引)
或者模糊查詢
SELECT * FROM table_name WHERE column_1 LIKE '%三'
SELECT * FROM table_name WHERE column_1 LIKE '三%'
SELECT * FROM table_name WHERE column_1 LIKE '%三%'
SELECT * FROM table_name WHERE column_1 LIKE '_好_'
如果要表示在字符串中既有A又有B，那么查詢語句為：
SELECT * FROM table_name WHERE column_1 LIKE '%A%' AND column_1 LIKE '%B%';
SELECT * FROM table_name WHERE column_1 LIKE '[張李王]三'; //表示column_1中有匹配張三、李三、王三的都可以
SELECT * FROM table_name WHERE column_1 LIKE '[^張李王]三'; //表示column_1中有匹配除了張三、李三、王三的其他三都可以
在模糊查詢中，%表示任意0個或多個字符；_表示任意單個字符（有且僅有），通常用來限制字符串長度;[]表示其中的某一個字符；[^]表示除了其中的字符的所有字符
或者在全文索引中模糊查詢
SELECT * FROM table_name WHERE MATCH(content) AGAINST('word1','word2',...);
刪除索引
DROP INDEXmy_index ON tablename；
或者
ALTER TABLEtable_name DROP INDEX index_name;
查看表中的索引
SHOW INDEX FROM tablename
查看查詢語句使用索引的情況
explain SELECT* FROMtable_name WHERE column_1='123';
優(yōu)勢：可以快速檢索，減少I/O次數(shù)，加快檢索速度；根據(jù)索引分組和排序，可以加快分組和排序；
劣勢：索引本身也是表，因此會占用存儲空間，一般來說，索引表占用的空間的數(shù)據(jù)表的1.5倍；索引表的維護和創(chuàng)建需要時間成本，這個成本隨著數(shù)據(jù)量增大而增大；構(gòu)建索引會降低數(shù)據(jù)表的修改操作（刪除，添加，修改）的效率，因為在修改數(shù)據(jù)表的同時還需要修改索引表
常見的索引類型有：主鍵索引、唯一索引、普通索引、全文索引、組合索引
1、主鍵索引：即主索引，根據(jù)主鍵pk_clolum（length）建立索引，不允許重復，不允許空值；
ALTER TABLE 'table_name' ADD PRIMARY KEY pk_index('col')；
2、唯一索引：用來建立索引的列的值必須是唯一的，允許空值
ALTER TABLE 'table_name' ADD UNIQUE index_name('col')；
3、普通索引：用表中的普通列構(gòu)建的索引，沒有任何限制
ALTER TABLE 'table_name' ADD INDEX index_name('col')；
4、全文索引：用大文本對象的列構(gòu)建的索引（下一部分會講解）
ALTER TABLE 'table_name' ADD FULLTEXT INDEX ft_index('col')；
5、組合索引：用多個列組合構(gòu)建的索引，這多個列中的值不允許有空值
ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3')；
組合索引相當于建立了col1,col1col2,col1col2col3三個索引，而col2或者col3是不能使用索引的
*在使用組合索引的時候可能因為列名長度過長而導致索引的key太大，導致效率降低，在允許的情況下，可以只取col1和col2的前幾個字符作為索引
ALTER TABLE 'table_name' ADD INDEX index_name(col1(4),col2（3))；
使用col1的前4個字符和col2的前3個字符作為索引
索引的實現(xiàn)原理
MySQL數(shù)據(jù)庫支持多種索引類型，如BTree索引，B+Tree索引，哈希索引，全文索引等等。
哈希索引
只有memory（內(nèi)存）存儲引擎支持哈希索引，哈希索引用索引列的值計算該值的hashCode，然后在hashCode相應(yīng)的位置存執(zhí)該值所在行數(shù)據(jù)的物理位置，因為使用散列算法，因此訪問速度非?？?，但是一個值只能對應(yīng)一個hashCode，而且是散列的分布方式，因此哈希索引不支持范圍查找和排序的功能。
全文索引
對于文本的大對象，或者較大的CHAR類型的數(shù)據(jù)，如果使用普通索引，那么匹配文本前幾個字符還是可行的，但是想要匹配文本中間的幾個單詞，那么就要使用LIKE %word%來匹配，這樣需要很長的時間來處理，響應(yīng)時間會大大增加，可使用時FULLTEXT索引了，在生成FULLTEXT索引時，會為文本生成一份單詞的清單，在索引時及根據(jù)這個單詞的清單來索引。
語法：
SELECT* FROMtable_name MATCH(ft_index) AGAINST('查詢字符串');
BTree索引
平衡搜索多叉樹。為磁盤等外存儲設(shè)備設(shè)計的一種平衡查找樹。
系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存時是以磁盤塊（block）為基本單位的，位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來，而不是需要什么取什么。
InnoDB存儲引擎中有頁（Page）的概念，頁是其磁盤管理的最小單位。InnoDB存儲引擎中默認每個頁的大小為16KB，可通過參數(shù)innodb_page_size將頁的大小設(shè)置為4K、8K、16K。查看MySql中頁的大?。?/p>
show variables like 'innodb_page_size'
而系統(tǒng)一個磁盤塊的存儲空間往往沒有這么大，因此InnoDB每次申請磁盤空間時都會是若干地址連續(xù)磁盤塊來達到頁的大小16KB。InnoDB在把磁盤數(shù)據(jù)讀入到磁盤時會以頁為基本單位，在查詢數(shù)據(jù)時如果一個頁中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置，這將會減少磁盤I/O次數(shù)，提高查詢效率。
B-Tree結(jié)構(gòu)的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤塊。為了描述B-Tree，首先定義一條記錄為一個二元組[key, data] ，key為記錄的鍵值，對應(yīng)表中的主鍵值，data為一行記錄中除主鍵外的數(shù)據(jù)。對于不同的記錄，key值互不相同。
3階B Tree
一棵m階的B-Tree有如下特性：
1. 每個節(jié)點最多有m個孩子。
2. 除了根節(jié)點和葉子節(jié)點外，其它每個節(jié)點至少有Ceil(m/2)個孩子。
3. 若根節(jié)點不是葉子節(jié)點，則至少有2個孩子
4. 所有葉子節(jié)點都在同一層，且不包含其它關(guān)鍵字信息
5. 每個非終端節(jié)點包含n個關(guān)鍵字信息（P0,P1,…Pn, k1,…kn）
6. 關(guān)鍵字的個數(shù)n滿足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)為關(guān)鍵字，且關(guān)鍵字升序排序。
8. Pi(i=1,…n)為指向子樹根節(jié)點的指針。P(i-1)指向的子樹的所有節(jié)點關(guān)鍵字均小于ki，但都大于k(i-1)
3階B Tree 例子：
每個節(jié)點占用一個盤塊的磁盤空間，一個節(jié)點上有兩個升序排序的關(guān)鍵字和三個指向子樹根節(jié)點的指針，指針存儲的是子節(jié)點所在磁盤塊的地址。兩個關(guān)鍵詞劃分成的三個范圍域?qū)?yīng)三個指針指向的子樹的數(shù)據(jù)的范圍域。以根節(jié)點為例，關(guān)鍵字為17和35，P1指針指向的子樹的數(shù)據(jù)范圍為小于17，P2指針指向的子樹的數(shù)據(jù)范圍為17~35，P3指針指向的子樹的數(shù)據(jù)范圍為大于35。
模擬查找關(guān)鍵字29的過程：
? 根據(jù)根節(jié)點找到磁盤塊1，讀入內(nèi)存?！敬疟PI/O操作第1次】
? 比較關(guān)鍵字29在區(qū)間（17,35），找到磁盤塊1的指針P2。
? 根據(jù)P2指針找到磁盤塊3，讀入內(nèi)存。【磁盤I/O操作第2次】
? 比較關(guān)鍵字29在區(qū)間（26,30），找到磁盤塊3的指針P2。
? 根據(jù)P2指針找到磁盤塊8，讀入內(nèi)存。【磁盤I/O操作第3次】
? 在磁盤塊8中的關(guān)鍵字列表中找到關(guān)鍵字29。
分析上面過程，發(fā)現(xiàn)需要3次磁盤I/O操作，和3次內(nèi)存查找操作。由于內(nèi)存中的關(guān)鍵字是一個有序表結(jié)構(gòu)，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。B-Tree相對于AVLTree縮減了節(jié)點個數(shù)，使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢效率。
B+Tree索引
B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結(jié)構(gòu)，InnoDB存儲引擎就是用B+Tree實現(xiàn)其索引結(jié)構(gòu)。
B-Tree結(jié)構(gòu)圖中可以看到每個節(jié)點中不僅包含數(shù)據(jù)的key值，還有data值。而每一個頁的存儲空間是有限的，如果<u>data數(shù)據(jù)較大時將會導致每個節(jié)點（即一個頁）能存儲的key的數(shù)量很小，當存儲的數(shù)據(jù)量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數(shù)，進而影響查詢效率</u>。
在B+Tree中，所有數(shù)據(jù)記錄節(jié)點都是按照鍵值大小順序存放在同一層的葉子節(jié)點上，而<u>非葉子節(jié)點上只存儲key值信息，這樣可以大大加大每個節(jié)點存儲的key值數(shù)量，降低B+Tree的高度</u>。
B+Tree相對于B-Tree有幾點不同：
非葉子節(jié)點只存儲鍵值信息。
所有葉子節(jié)點之間都有一個鏈指針。
數(shù)據(jù)記錄都存放在葉子節(jié)點中。
通常在B+Tree上有<u>兩個頭指針，一個指向根節(jié)點，另一個指向關(guān)鍵字最小的葉子節(jié)點</u>，而且所有葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈式環(huán)結(jié)構(gòu)。因此可以對B+Tree進行兩種查找運算：一種是<u>對于主鍵的范圍查找和分頁查找</u>，另一種是從根節(jié)點開始，進行<u>隨機查找</u>。
InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT（占用4個字節(jié)）或BIGINT（占用8個字節(jié)），指針類型也一般為4或8個字節(jié)，也就是說一個頁（B+Tree中的一個節(jié)點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值，為方便計算，這里的K取值為103）。也就是說一個深度為3的B+Tree索引可以維護103 * 10^3 * 10^3 = 10億 條記錄。
實際情況中每個節(jié)點可能不能填充滿，因此在數(shù)據(jù)庫中，B+Tree的高度一般都在2~4層。<u>mysql</u><u>的InnoDB存儲引擎在設(shè)計時是將根節(jié)點常駐內(nèi)存的</u>，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。
數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）。上面的B+Tree示例圖在數(shù)據(jù)庫中的實現(xiàn)即為聚集索引，聚集索引的B+Tree中的葉子節(jié)點存放的是整張表的行記錄數(shù)據(jù)。輔助索引與聚集索引的區(qū)別在于<u>輔助索引的葉子節(jié)點并不包含行記錄的全部數(shù)據(jù)，而是存儲相應(yīng)行數(shù)據(jù)的聚集索引鍵，即主鍵</u>。當通過輔助索引來查詢數(shù)據(jù)時，<u>InnoDB存儲引擎會遍歷輔助索引找到主鍵，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)</u>。
B+ Tree
