當著小萌新之際，最近作業中遇到了mysql優化的相關問題，然后既然提到了優化，很多像我這樣的小萌新不容置喙，肯定張口就是 建立索引 之類的，
那么說到底，索引到底是什么，它是怎么作業的？接下來就讓我和大家一起學習學習吧
1.索引是什么？
不難理解，索引的出現其實就是為了提高資料查詢的效率，簡單點來說索引就好比一本書的目錄，是為了準確定位具體資料而用的，
2.索引的常見模型
索引模型中，一般比較常見的包括 哈希表、有序陣列、搜索樹
哈希表是一種以key-value存盤資料的結構，我們只要輸入待查找的值即 key， 就可以找到其對應的值即 Value，哈希的思路很簡單，把值放在陣列里，用一個哈希函式把 key 換算成一個確定的位置，然后把 value 放在陣列的這個位置，
但是當多個 key 值經過哈希函式的換算，會出現同一個值的情況，為了處理這種情況，引出了 鏈表
如果你要維護一個身份證資訊和姓名的表，需要根據身份證號查找對應的名字，這時 對應的哈希索引的示意圖如下所示
圖中，User2 和 User3 根據身份證號算出來的值都是 n，后面還跟了一個鏈表，
如果這時候你要查 card-2 對應的名字是什么，處理步驟就是：首先，將 card-2 通過哈希函式算出n,然后，按順序遍歷，找到 User2，
需要注意的是，圖中四個 card-n 的值并不是遞增的，這樣做的好處是增加新的 User 時 速度會很快，只需要往后追加，
但缺點是，因為不是有序的，所以哈希索引做 區間查詢 的速度是很慢的，
如果你現在要找身份證號在 [card_X, card_Y] 這個區間的所有用戶，就必須全部掃描一遍了，
所以，哈希表這種結構適用于只有等值查詢的場景，比如 Memcached 及其他一些 NoSQL 引擎
有序陣列在等值查詢和范圍查詢場景中的性能就都非常優秀,以下是其索示意圖
假設身份證號沒有重復，這個陣列就是按照身份證號遞增的順序保存的，
這時候如 果你要查 card_n2 對應的名字，用二分法就可以快速得到，這個時間復雜度是 O(log(N))，
同時很顯然，這個索引結構支持范圍查詢，你要查身份證號在 [card_X, card_Y] 區間的user，可以先用二分法找到 card_X（如果不存在card_X，就找到大于card_X 的第一個user），然后向右遍歷，直到查到第一個大于card_Y 的身份證 號，退出回圈，
如果僅僅看查詢效率，有序陣列就是最好的資料結構了，
但是，在需要更新資料的時候卻不好，你往中間插入一個記錄就必須得挪動后面所有的記錄，成本太高，
所以，有序陣列索引只適用于靜態存盤引擎，比如你要保存的是2020年某個城市的所有人口資訊，這類不會再修改的資料
二叉搜索樹示意圖
二叉搜索樹的特點是：
每個節點的左兒子小于父節點，父節點又小于右兒子，這樣如果你要查card_n2 的話，按照圖中的搜索順序就是按照 UserA -> UserC -> UserF -> User2 這個路徑得到，這個時間復雜度是 O(log(N))，
當然為了維持 O(log(N)) 的查詢復雜度，你就需要保持這棵樹是平衡二叉樹，為了做這個 保證，更新的時間復雜度也是 O(log(N))，
樹可以有二叉，也可以有多叉，多叉樹就是每個節點有多個兒子，兒子之間的大小保證從左 到右遞增，
二叉樹是搜索效率最高的，但是實際上大多數的資料庫存盤卻并不使用二叉樹， 其原因是，索引不止存在記憶體中，還要寫到磁盤上，
你可以想象一下一棵 100 萬節點的平衡二叉樹，樹高20，一次查詢可能需要訪問 20 個資料塊，
在機械硬碟時代，從磁盤隨機讀一個資料塊需要 10 ms 左右的尋址時間，也就是說，對于一個100萬行的表，如果使用二叉樹來存盤，單獨訪問一個行可能需要 20 個10 ms 的時間
為了讓一個查詢盡量少地讀磁盤，就必須讓查詢程序訪問盡量少的資料塊，那么，我們就不應該使用二叉樹，而是要使用“N 叉”樹，這里，“N 叉”樹中的“N”取決于資料塊的大小，
以 InnoDB 的一個整數欄位索引為例，這個N差不多是 1200，這棵樹高是 4 的時候，就可以存 1200 的 3 次方個值，這已經 17 億了，
考慮到樹根的資料塊總是在記憶體中的，一個 10 億行的表上一個整數欄位的索引，查找一個值最多只需要訪問3次磁盤，
其實，樹的第二層也有很大概率在記憶體中，那么訪問磁盤的平均次數就更少了，N叉樹由于在讀寫上的性能優點，以及適配磁盤的訪問模式，已經被廣泛應用在資料庫引 擎中了，
在 MySQL 中，索引是在存盤引擎層實作的，所以并沒有統一的索引標準，即不同存盤引 擎的索引的作業方式并不一樣，而即使多個存盤引擎支持同一種型別的索引，其底層的實作 也可能不同，由于 InnoDB 存盤引擎在 MySQL 資料庫中使用最為廣泛，下面以 InnoDB為例子
InnoDB 的索引模型
在 InnoDB 中，表都是根據主鍵順序以索引的形式存放的，這種存盤方式的表稱為索引組織表，
InnoDB 使用了 B+ 樹索引模型，所以資料都是存盤在 B+ 樹中的，每一個索引在 InnoDB 里面對應一棵 B+ 樹，
假設，我們有一個主鍵列為 ID 的表，表中有欄位 k，并且在 k 上有索引
CREATE TABLE T ( id INT PRIMARY KEY, k INT NOT NULL, NAME VARCHAR ( 16 ), INDEX ( k ) ) ENGINE = INNODB;
表中 R1~R5 的 (ID,k) 值分別為 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，兩棵樹 的示例示意圖如下
從圖中不難看出，根據葉子節點的內容，索引型別分為 主鍵索引 和 非主鍵索引 ，
主鍵索引的葉子節點存的是整行資料，在 InnoDB 里，主鍵索引也被稱為聚簇索引 （clustered index），
非主鍵索引的葉子節點內容是主鍵的值，在 InnoDB 里，非主鍵索引也被稱為二級索引 （secondary index），
根據上面的索引結構說明，來討論一個問題：基于主鍵索引和普通索引的查詢有什么區別？
如果陳述句是 select * from T where ID=500，即主鍵查詢方式，則只需要搜索 ID 這棵 B+ 樹；
如果陳述句是 select * from T where k=5，即普通索引查詢方式，則需要先搜索 k 索引 樹，得到 ID 的值為 500，再到 ID 索引樹搜索一次，
這個程序稱為回表，
也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹，因此，我們在應用中應該盡量使用主鍵查詢，.
索引維護
B+樹為了維護索引有序性，在插入新值的時候需要做必要的維護，
以上面這個圖為例，
如果插入新的行ID值為 700，則只需要在 R5 的記錄后面插入一個新記錄，
如果新插入的ID值為400，就相對麻煩了，需要邏輯上挪動后面的資料，空出位置，
而更糟的情況是，如果 R5 所在的資料頁已經滿了，根據 B+ 樹的演算法，這時候需要申請一個新的資料頁，然后挪動部分資料過去，
這個程序稱為頁分裂，在這種情況下，性能自然會受影響，
除了性能外，頁分裂操作還影響資料頁的利用率，原本放在一個頁的資料，現在分到兩個頁中，整體空間利用率降低大約50%，
基于上面的索引維護程序說明，討論一個案例：
在一些建表規范里面見到過類似的描述，要求建表陳述句里一定要有自 增主鍵，
分析一下哪些場景下應該使用自增主鍵，而 哪些場景下不應該，
自增主鍵是指自增列上定義的主鍵，在建表陳述句中一般是這么定義的： NOT NULL PRIMARY KEY AUTO_INCREMENT，
插入新記錄的時候可以不指定 ID 的值，系統會獲取當前 ID 最大值加 1 作為下一條記錄的 ID 值，
也就是說，自增主鍵的插入資料模式，正符合了我們前面提到的遞增插入的場景，每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂，
而有業務邏輯的欄位做主鍵，則往往不容易保證有序插入，這樣寫資料成本相對較高，
除了考慮性能外，還可以從存盤空間的角度來看，
假設你的表中確實有一個唯一欄位， 比如字串型別的身份證號，那應該用身份證號做主鍵，還是用自增欄位做主鍵呢？
由于每個非主鍵索引的葉子節點上都是主鍵的值（因為要根據非主鍵索引找到主鍵索引位置然后再找到資料，可看上圖），
如果用身份證號做主鍵，那么每個二級索引的葉子節點占用約 20 個位元組，而如果用整型做主鍵，則只要 4 個位元組，如果是長整型 （bigint）則是 8 個位元組，
顯然，主鍵長度越小，普通索引的葉子節點就越小，普通索引占用的空間也就越小，
所以，從性能和存盤空間方面考量，自增主鍵往往是更合理的選擇，
什么場景適合用業務欄位直接做主鍵的呢？有些業務的場景需求是如下：
- 只有一個索引；
- 該索引必須是唯一索引
這就是典型的 KV 場景，
由于沒有其他索引，所以也就不用考慮其他索引的葉子節點大小的問題，
這時候我們就要優先考慮上一段提到的“盡量使用主鍵查詢”原則，直接將這個索引設定為 主鍵，可以避免每次查詢需要搜索兩棵樹，
對于上面例子中的 InnoDB 表 T，如果要重建索引 k，可以寫：
alter table T drop index k;
alter table T add index(k);
要重建主鍵索引，可以寫
alter table T drop primary key;
alter table T add primary key(id);
這樣寫是否合理？
重建索引 k 的做法是合理的，可以達到省空間的目的，
但是，重建主鍵的程序不合理，
不論是洗掉主鍵還是創建主鍵，都會將整個表重建，
所以連著執行這兩個陳述句的話，第一個陳述句就白做了，這兩個陳述句，可以用這個陳述句代替 ：alter table T engine=InnoDB
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/199921.html
標籤：其他