MySQL的索引操作及底層結構淺析

一.索引

? ? ? ? 提高數據庫的性能，索引是物美價廉的東西了。不用加內存，不用改程序，不用調sql，只要執行正確的 create index ，查詢速度就可能提高成百上千倍。但是天下沒有免費的午餐，查詢速度的提高是以插入、更新、刪除的速度為代價的，這些寫操作，增加了大量的IO。所以它的價值，在于提高一個海量數據的檢索速度。

1.1mysql與磁盤交互的基本單位

? ? ? ? 內存與磁盤的基本交互單位通常為頁（如4KB），訪問一個字節時，若其所在頁未加載，操作系統會將該頁全部加載到內存，這體現了空間局部性原理。

? ? ? ? 而 MySQL 作為一款應用軟件，可以想象成一種特殊的文件系統。它有著更高的IO場景，所以，為了提高基本的IO效率， MySQL 進行IO的基本單位是 16KB.

我們可以使用SHOW GLOBAL STATUS LIKE 'innodb_page_size';來查看當前mysql的IO基本交互單位的大小(我們后面統一基于innodb進行講解):

????????磁盤這個硬件設備的基本單位是 512 字節，而 MySQL InnoDB引擎使用 16KB 進行IO交互。即， MySQL 和磁盤進行數據交互的基本單位是 16KB 。這個基本數據單元，在 MySQL 這里叫做page(注意和系統的page區分).

我們先來理清下mysql進行IO的過程:

MySQL 中的數據文件，是以page為單位保存在磁盤當中的。
MySQL 的 CURD 操作，都需要通過計算，找到對應的插入位置，或者找到對應要修改或者查詢的數據。
而只要涉及計算，就需要CPU參與，而為了便于CPU參與，一定要能夠先將數據移動到內存當中。所以在特定時間內，數據一定是磁盤中有，內存中也有。后續操作完內存數據之后，以特定的刷新策略，刷新到磁盤。而這時，就涉及到磁盤和內存的數據交互，也就是IO了。而此時IO的基本單位就是Page。

????????為了更好的進行上面的操作， MySQL 服務器在內存中運行的時候，在服務器內部，就申請了被稱為 Buffer Pool 的的大內存空間，來進行各種緩存。其實就是很大的內存空間，來和磁盤數據進行IO交互。

理解一下什么是隨機訪問與連續訪問:
隨機訪問：本次IO所給出的扇區地址和上次IO給出扇區地址不連續，這樣的話磁頭在兩次IO操作之間需要作比較大的移動動作才能重新開始讀/寫數據。

連續訪問：如果當次IO給出的扇區地址與上次IO結束的扇區地址是連續的，那磁頭就能很快的開始這次IO操作，這樣的多個IO操作稱為連續訪問。

? ? ? ??對于沒有索引的查詢，必須加載整個表的數據頁到Buffer Pool,在沒有索引的情況下查找特定數據會產生大量隨機磁盤訪問.非常的耗時間,如何更加高效的利用mysql的buffer pool呢?索引的作用正是為了解決這些問題.我們先來看看索引是什么:

1.2索引的理解

????????常見的索引有主鍵索引,唯一鍵索引,普通索引與全文索引(主鍵索引和唯一鍵索引只要我們創建了相對應的鍵便會自動基于鍵列生成索引).我們之前說過,表在不給主鍵的時候,會默認生成索引,所以表默認是有索引的也就是主鍵索引.我們先來看一個對于主鍵索引的樣例:

create table if not exists user (id int primary key, --一定要添加主鍵哦，只有這樣才會默認生成主鍵索引age int not null,name varchar(16) not null
);
mysql> show create table user \G
*************************** 1. row ***************************
Table: user
Create Table: CREATE TABLE `user` (`id` int(11) NOT NULL,`age` int(11) NOT NULL,`name` varchar(16) NOT NULL,PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 --默認就是InnoDB存儲引擎
1 row in set (0.00 sec)

然后我們插入一組無序的數據:

--插入多條記錄，注意，我們并沒有按照主鍵的大小順序插入
mysql> insert into user (id, age, name) values(3, 18, '楊過');
Query OK, 1 row affected (0.01 sec)
mysql> insert into user (id, age, name) values(4, 16, '小龍女');
Query OK, 1 row affected (0.00 sec)
mysql> insert into user (id, age, name) values(2, 26, '黃蓉');
Query OK, 1 row affected (0.01 sec)
mysql> insert into user (id, age, name) values(5, 36, '郭靖');
Query OK, 1 row affected (0.00 sec)
mysql> insert into user (id, age, name) values(1, 56, '歐陽鋒');
Query OK, 1 row affected (0.00 sec)

查看結果的時候卻發現他們自動就是有序的了:

mysql> select * from user; --發現竟然默認是有序的！是誰干的呢？排序有什么好處呢？
+----+-----+-----------+
| id | age | name |
+----+-----+-----------+
| 1 | 56 | 歐陽鋒 |
| 2 | 26 | 黃蓉 |
| 3 | 18 | 楊過 |
| 4 | 16 | 小龍女 |
| 5 | 36 | 郭靖 |
+----+-----+-----------+
5 rows in set (0.00 sec)

理解單張page?

ok在此中斷一下,我們上面說了mysql與磁盤的基本交互單位為page,他是基于局部性原理這么做的.mysql中有許多表,而要管理好這些文件就需要先描述再組織,我們目前可以簡單理解成一個個獨立文件是有一個或者多個Page構成的。

????????不同的 Page ，在 MySQL 中，都是 16KB ，使用 prev 和 next 構成雙向鏈表.因為有主鍵的問題， MySQL 會默認按照主鍵給我們的數據進行排序，從上面的Page內數據記錄可以看出，數據是有序且彼此關聯的。
為什么數據庫在插入數據時要對其進行排序呢？我們按正常順序插入數據不是也挺好的嗎？插入數據時排序的目的，就是優化查詢的效率。頁內部存放數據的模塊，實質上也是一個鏈表的結構，鏈表的特點也就是增刪快，查詢修改慢，所以優化查詢的效率是必須的。也正是因為有序，在查找的時候，從頭到后都是有效查找，沒有任何一個查找是浪費的，而且，如果運氣好，是可以提前結束查找過程的。

理解多張page

????????通過上面的分析，我們知道，上面頁模式中，只有一個功能，就是整頁的數據加載到內存中，以減少硬盤IO次數，從而提高性能。但是，我們也可以看到，現在的頁模式內部，實際上是采用了鏈表的結構，前一條數據指向后一條數據，本質上還是通過數據的逐條比較來取出特定的數據。

????????如果有1千萬條數據，一定需要多個Page來保存1千萬條數據，多個Page彼此使用雙鏈表鏈接起來，而且每個Page內部的數據也是基于鏈表的。那么，查找特定一條記錄，也一定是線性查找。這效率也太低了。

頁目錄?

? ? ? ? 我們平常看書的時候,在起始頁面總有幾頁是目錄.有了目錄,我們便可以通過目錄快速找到目標頁.而表數據查詢本質上是一個篩選淘汰的過程，其效率取決于每次查詢能夠排除的無效數據量。那么我們可不可以在mysql中也為每張表內部添加上目錄結構,mysql就是這樣做的(我們這里說的是innodb引擎):

? ? ? ? 誠然,單張page在添加了目錄之后,雖然損耗了一定的空間,但是極大的提高了在單張頁中的查詢效率.可是,多張page呢?軟件設計中存在一個悖論：遇到無法解決的問題時，我們總是傾向于添加中間層來解決。若問題仍未解決，就繼續疊加中間層。所以,我們可以在所有page的上一層,添加一層頁目錄,像多叉樹那樣:

但是如果多添加一層還不夠呢?那就再加一層!:

? ? ? ? 而多出來的所有層所有的page中,不存儲數據(innodb),只存儲目錄.這其實也就是對高階數據結構的使用-B+樹.隨便找一個id=？我們發現，現在查找的Page數一定減少了，也就意味著IO次數減少了，那么效率也就提高了。
所以我們可以總結一下,在innodb引擎中:

Page分為目錄頁和數據頁。目錄頁只放各個下級Page的最小鍵值。
查找的時候，自定向下找，只需要加載部分目錄頁到內存，即可完成算法的整個查找過程，大大減少了IO次數

?InnoDB 在建立索引結構來管理數據的時候，其他數據結構為何不行？

鏈表當然是不行的,我們上面也說過.
二叉搜索樹？退化問題，可能退化成為線性結構
AVL &&紅黑樹？雖然是平衡或者近似平衡，但是畢竟是二叉結構，相比較多階B+，意味著樹整體過高，大家都是自頂向下找，層高越低，意味著系統與硬盤更少的IO Page交互。雖然你很秀，但是有更秀的。
Hash？官方的索引實現方式中， MySQL 是支持HASH的，不過 InnoDB 和 MyISAM 并不支持.Hash跟進其算法特征，決定了雖然有時候也很快(O(1))，不過，在面對范圍查找就明顯不行，另外還有其他差別，有興趣可以查一下。
B樹？最值得比較的是 InnoDB 為何不用B樹作為底層索引

B+ vs B

B樹:?

B+樹:

B樹節點，既有數據，又有Page指針，而B+，只有葉子節點有數據，其他目錄頁，只有鍵值Page指針
B+葉子節點，全部相連，而B沒有(利好范圍查找).

所以我們就可以理解為什么選擇B+樹了:

節點不存儲data，這樣一個節點就可以存儲更多的key。可以使得樹更矮，所以IO操作次數更少。
葉子節點相連，更便于進行范圍查找

Innodb和MyIsam都使用的是B+樹,那么他們有什么區別呢?

聚簇索引(Innodb)與非聚簇索引(MyISAM)

MyISAM 引擎同樣使用B+樹作為索引結果，葉節點的data域存放的是數據記錄的地址。下圖為 MyISAM表的主索引， Col1 為主鍵:

其中， MyISAM 最大的特點是，將索引Page和數據Page分離，也就是葉子節點沒有數據，只有對應數據的地址。相較于 InnoDB 索引， InnoDB 是將索引和數據放在一起的。

--終端A
mysql> create database myisam_test; --創建數據庫
Query OK, 1 row affected (0.00 sec)
mysql> use myisam_test;
Database changed
mysql> create table mtest(
-> id int primary key,
-> name varchar(11) not null
-> )engine=MyISAM; --使用engine=MyISAM
Query OK, 0 rows affected (0.01 sec)
--終端B
[root@VM-0-3-centos mysql]# ls myisam_test/ -al --mysql數據目錄下
total 28
drwxr-x--- 2 mysql mysql 4096 Jun 13 13:33 .
drwxr-x--x 13 mysql mysql 4096 Jun 13 13:32 ..
-rw-r----- 1 mysql mysql 61 Jun 13 13:32 db.opt
-rw-r----- 1 mysql mysql 8586 Jun 13 13:33 mtest.frm --表結構數據
-rw-r----- 1 mysql mysql 0 Jun 13 13:33 mtest.MYD --該表對應的數據，當前沒有數
據，所以是0
-rw-r----- 1 mysql mysql 1024 Jun 13 13:33 mtest.MYI --該表對應的主鍵索引數據

--終端A
mysql> create database innodb_test; --創建數據庫
Query OK, 1 row affected (0.00 sec)
mysql> use innodb_test;
Database changed
mysql> create table itest(
-> id int primary key,
-> name varchar(11) not null
-> )engine=InnoDB; --使用engine=InnoDB
Query OK, 0 rows affected (0.02 sec)
--終端B
[root@VM-0-3-centos mysql]# ls innodb_test/ -al
total 120
drwxr-x--- 2 mysql mysql 4096 Jun 13 13:39 .
drwxr-x--x 14 mysql mysql 4096 Jun 13 13:38 ..
-rw-r----- 1 mysql mysql 61 Jun 13 13:38 db.opt
-rw-r----- 1 mysql mysql 8586 Jun 13 13:39 itest.frm --表結構數據
-rw-r----- 1 mysql mysql 98304 Jun 13 13:39 itest.ibd --該表對應的主鍵索引和用戶
數據，雖然現在一行數據沒有，但是該表并不為0，因為有主鍵索引數據

????????當然， MySQL 除了默認會建立主鍵索引外，我們用戶也有可能建立按照其他列信息建立的索引，一般這種索引可以叫做輔助（普通）索引。對于 MyISAM ,建立輔助（普通）索引和主鍵索引沒有差別，無非就是主鍵不能重復，而非主鍵可重復.

同樣， InnoDB 除了主鍵索引，用戶也會建立輔助（普通）索引，我們以上表中的 Col3 建立對應的輔助索引如下圖：

可以看到， InnoDB 的非主鍵索引中葉子節點并沒有數據，而只有對應記錄的key值。所以通過輔助（普通）索引，找到目標記錄，需要兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。這種過程，就叫做回表查詢.

1.3索引的操作

我們這里只介紹下主鍵,唯一鍵與普通索引.其他的索引諸如全文索引讀者可自行進行了解.?

1.3.1主鍵索引?

主鍵索引的創建方式一共有三種:

-- 在創建表的時候，直接在字段名后指定 primary key
create table user1(id int primary key, name varchar(30));-- 在創建表的最后，指定某列或某幾列為主鍵索引
create table user2(id int, name varchar(30), primary key(id));create table user3(id int, name varchar(30));
-- 創建表以后再添加主鍵
alter table user3 add primary key(id);

主鍵索引的特點:

一個表中，最多有一個主鍵索引，當然可以使符合主鍵
主鍵索引的效率高（主鍵不可重復）
創建主鍵索引的列，它的值不能為null，且不能重復
主鍵索引的列基本上是int

1.3.2唯一索引

唯一索引創建方式也有三種:

-- 在表定義時，在某列后直接指定unique唯一屬性。
create table user4(id int primary key, name varchar(30) unique);-- 創建表時，在表的后面指定某列或某幾列為unique
create table user5(id int primary key, name varchar(30), unique(name));create table user6(id int primary key, name varchar(30)）；
alter table user6 add unique(name);

?唯一索引的特點：

一個表中，可以有多個唯一索引
查詢效率高
如果在某一列建立唯一索引，必須保證這列不能有重復數據
如果一個唯一索引上指定not null，等價于主鍵索引

1.3.3普通索引?

create table user8(id int primary key,name varchar(20),email varchar(30),index(name) --在表的定義最后，指定某列為索引
);create table user9(id int primary key, name varchar(20), email varchar(30));
alter table user9 add index(name); --創建完表以后指定某列為普通索引create table user10(id int primary key, name varchar(20), email varchar(30));
-- 創建一個索引名為 idx_name 的索引
create index idx_name on user10(name);

普通索引的特點：