一、什麼是索引？
索引就好比字典的目錄一樣
我們通常都會先去目錄查找關鍵偏旁或者字母再去查找
要比直接翻查字典查詢要快很多
二、為什麼要有索引？
然而我們在使用mysql資料庫的時候也像字典一樣有索引的情況下去查詢，肯定速度要快很多
2.1問題：
1.mysql資料存儲在什麼地方?
磁盤
2.查詢資料慢，一般卡在哪？
IO
3.去磁盤讀取資料，是用多少讀取多少嗎？
磁盤預讀
局部性原理：資料和程式都有聚內建群的傾向，同時之前被通路過的資料很可能再次被查詢，空間局部性，時間局部性
磁盤預讀：記憶體和磁盤發生資料互動的時候，一般情況下有一個最小的邏輯單元，頁。 頁一般由作業系統覺得大小，4k或8k，而我們在進行資料互動的時候，可以取頁的整數倍來讀取。關注公衆号：程式員追風，回複 012 即可擷取一份578頁PDF文檔的MySQL學習筆記
innodb存儲引擎每次讀取資料，讀取16k
4.索引存儲在哪？
磁盤，查詢資料的時候會優先将索引加載到記憶體中
5.索引在存儲的時候，需要什麼資訊？需要存儲存儲什麼字段值？
key:實際資料行中存儲的值
檔案位址
offset：偏移量
6.這種格式的資料要使用什麼樣的資料結構來進行存儲？
key-values
哈希表，樹(二叉樹、紅黑樹、AVL樹、B樹、B+樹)
7.mysql索引系統中不是按照剛剛說的格式存儲的，為什麼？
OLAP:聯機分析處理----對海量曆史資料進行分析，産生決策性的政策----資料倉庫—Hive
OLTP:聯機事務處理----要求很短時效内傳回對應的結果----資料庫—關系型資料庫(mysql、oracle)
三、mysql的索引資料結構
3.1哈希表:
HashMap數組加連結清單的結構，不适合作為索引的原因：
1.哈希沖突會造成資料散列不均勻，會産生大量的線性查詢，比較浪費時間
2.不支援範圍查詢，當進行範圍查詢的時候，必須挨個周遊
3.對于記憶體空間的要求比較高
優點： 如果是等值查詢，非常快
在mysql中有沒有hash索引?
1.memory存儲引擎使用的是hash索引
2.innodb支援自适應hash
create table test(id int primary key,name varchar(30))
engine='innodb/memory/myisam'
-- 5.1之後預設innodb
3.2樹：
樹這種資料結構有很多，我們常見的有：
二叉樹、BST、AVL、紅黑樹、B樹、B+樹
①二叉樹：無序插入
這就是我們的樹的結構圖，但是二叉樹的資料插入是無序的，也就是說當需要查找的時候，還是得一個一個挨着去周遊查找
②BST(二叉搜尋樹)：
插入的資料有序，左子樹必須小于根節點，右子樹必須大于根節點--------使用二分查找來提高效率
這樣的話如果要查詢資料，可以通過二分查找，快速縮小範圍，減少了時間複雜度
但是如果插入的順序是升序或者降序的話，樹的形狀會變成如下：
此時二叉搜尋樹就會退化成連結清單，時間複雜度又會變成O(n)
③AVL：平衡二叉樹
為了解決上述問題，通過左旋轉或右旋轉讓樹平衡
最短子樹跟最長子樹高度隻差不能超過1
由圖我們可以看到，當順序插入的時候，會自動的進行旋轉，以達到平衡
但是會通過插入性能的損失來彌補查詢性能的提升
當我們插入的資料很多時候，而查詢很少的時候，由于插入資料會旋轉同樣會消耗很多時間
④紅黑樹(解決了讀寫請求一樣多)
同樣是經過左右旋讓樹平衡起來，還要變色的行為
最長子樹隻要不超過最短子樹的兩倍即可
查詢性能和插入性能近似取得平衡
但是随着資料的插入、發現樹的深度會變深，樹的深度會越來越深，意味着IO次數越多，影響資料讀取的效率
⑤ B樹
為了解決上述資料插入過多，樹深度變深的問題，我們采用B樹
把原來的有序二叉樹變成有序多叉樹
舉例： 如果要查詢select * from table where id=14？
- 第一步，将磁盤一加載到記憶體中，發現14<16,尋找位址磁盤2
- 第二步，将磁盤二加載到記憶體中，發現14>11,尋找位址磁盤7
-
第三步，将磁盤七加載到記憶體中，發現14=14，讀取data，取出data，結束
思考：B樹就是完美的嘛？
問題1： B樹不支援範圍查詢的快速查找，如果我們查詢一個範圍的資料，查找到範圍一個邊界時，需要回到根節點重新周遊查找，需要從根節點進行多次周遊，即便找到範圍的另一個邊界，查詢效率會降低。
問題2： 如果data存儲的是行記錄，行的大小随着列數的增多，所占空間會變大。這時，一個頁中可存儲的資料量就會變少，樹相應就會變高，磁盤IO次數就會變大。
思考2：三層B樹能夠存儲多少條記錄？
答: 假設一個data為1k，innodb存儲引擎一次讀取資料為16k，三層即161616=4096；
但是往往在開發中，一個表的資料要遠遠大于4096，難道要繼續加層，這樣豈不就加大了IO
四、為什麼使用B+樹？
實際存儲表資料的時候，怎麼存儲呢？
key
完整的資料行
改造B+樹
B+樹對B樹進行了改進，把資料全放在了葉子節點中，葉子節點之間使用雙向指針連接配接，最底層的葉子節點形成了一個雙向有序連結清單。
例如： 查詢範圍 select * from table where id between 11 and 35？
- 第一步，将磁盤一加載到記憶體中，發現11<28,尋找位址磁盤2
- 第二步，将磁盤二加載到記憶體中，發現10>11>17,尋找位址磁盤5
- 第三步，将磁盤五加載到記憶體中，發現11=11，讀取data
-
第四步，繼續向右查詢，讀取磁盤5，發現35=35，讀取11-35之間資料，結束
由此可見，這樣的範圍查詢比B樹速度提高了不少
對比B樹和B+樹？
- 葉子節點中才放資料
- 非葉子節點中不存儲資料
- B+樹每個節點包含更多個節點，這樣做的好處，可以降低樹的高度，同時将資料範圍變成多個區間，區間越多查詢越快
問題： 建立索引時用int還是varchar？
答：視情況而定，但是記住一定讓key越小越好
五、索引的建立
在建立索引之前，我先說一下存儲引擎
存儲引擎： 表示不同的資料在磁盤的不同表現形式
大家去觀察mysql的磁盤檔案會發現
innodb： innodb的資料和索引都存儲在一個檔案下.idb
myisam： myisam的索引存儲在.MYI檔案中，資料存儲在.MYD中
5.1聚簇索引和非聚簇索引
概念：判斷是否是聚簇索引就看資料和索引是否在一個檔案中
innodb：
- 隻能有一個聚簇索引，但是有很多非聚簇索引
- 向innodb插入資料的時候，必須要包含一個索引的key值
- 這個索引的key值，可以是主鍵，如果沒有主鍵，那麼就是唯一鍵，如果沒有唯一鍵，那麼就是一個自生成的6位元組的rowid
myisam： 非聚簇索引
MySQL—innodb----B+樹
索引和資料存儲在一起，找到索引即可讀取對應的資料
MySQL—myisam----B+樹
索引和存儲資料的位址在一起，找到索引得到位址值，再通過位址找到對應的資料
5.2回表
接下來，我會建立一張案例表給大家展示
CREATE TABLE user_test(
id INT PRIMARY KEY AUTO_INCREMENT,-- id為主鍵
uname VARCHAR(20) ,
age INT,
gender VARCHAR(10),
KEY `idx_uname` (`uname`) -- 索引選擇為名字
)ENGINE = INNODB;
INSERT INTO user_test VALUES(1,'張三',18,'男');
INSERT INTO user_test VALUES(NULL,'馬冬梅',19,'女');
INSERT INTO user_test VALUES(NULL,'趙四',18,'男');
INSERT INTO user_test VALUES(NULL,'王老七',22,'男');
INSERT INTO user_test VALUES(NULL,'劉燕',16,'女');
INSERT INTO user_test VALUES(NULL,'萬寶',26,'男');
select * from user_test where uname = '張三';
-- 當我們表中有主鍵索引的時候，我們再去設定一個uname為索引，那麼此時這條sql語句的查詢過程應該如下：
首先先根據uname查詢到id，再根據id查詢到行的資訊
這樣的操作走了兩棵B+樹，就是回表
當根據普通索引查詢到聚簇索引的key值之後，再根據key值在聚簇索引中擷取資料
我們可以發現這樣的操作是很浪費時間的，是以我們日常操作的時候，盡量減少回表的次數
5.3覆寫索引
select id,uname from table where uname = '張三';
-- 根據uname 可以直接查詢到id，uname兩個列的值，直接傳回即可
-- 不需要從聚簇索引查詢任何資料，此時叫做索引覆寫
5.4最左比對
-- 假設有一張表，有id，name，age，gender四個字段，id是主鍵，name，age是組合索引列
-- 組合索引使用的時候必須先比對name，然後比對age
select * from table where name = ? and age = ? ;-- 生效
select * from table where name = ?;-- 生效
select * from table where age = ? ;-- 不生效
select * from table where age = ? and name = ? ;-- 生效
--在mysql内部有優化器會調整對應的順序
5.5索引下推
select * from table where name = ? and age = ? ;
-- mysql裡的三層架構:
-- 用戶端:JDBC
-- 服務端:server
-- 存儲引擎:資料存儲
在沒有索引下推之前，根據name從存儲引擎中擷取符合規則的資料，在server層對age進行過濾
有索引下推之後，根據name、age兩個條件從存儲引擎中擷取對應的資料