你好，是我琉憶。

經常跟數據打交道的你，有沒有去考慮過數據上百萬，為什么它可以檢索那么快？

一說到數據庫的檢索速度這么快，我想你一定想到了索引。

沒錯，今天我們來簡單聊聊索引，聊聊索引是什么，怎么使用，有什么優缺點，它的工作原理，為什么它可以讓數據的檢索變得這么快。

01

索引是什么？

MYSQL官方對索引的定義為：索引(Index)是幫助MySQL高效獲取數據的數據結構，所以說索引的本質是：數據結構。

索引的目的在于提高查詢效率，可以類比字典、 火車站的車次表、圖書的目錄等 。

可以簡單的理解為“排好序的快速查找數據結構”，數據本身之外，數據庫還維護者一個滿足特定查找算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。下圖是一種可能的索引方式示例。左邊的數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值，和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在一定的復雜度內獲取到對應的數據，從而快速檢索出符合條件的記錄。

索引本身也很大，不可能全部存儲在內存中，一般以索引文件的形式存儲在磁盤上

平常說的索引，沒有特別指明的話，就是B+樹(多路搜索樹，不一定是二叉樹)結構組織的索引。其中聚集索引，次要索引，覆蓋索引，符合索引，前綴索引，唯一索引默認都是使用B+樹索引，統稱索引。此外還有哈希索引等。

我們接下來講講索引的使用。

02

索引的使用

在創建表的時候添加索引

CREATE TABLE mytable( ID INT NOT NULL, username VARCHAR(16) NOT NULL, INDEX [indexName] (username(length)) );

在創建表以后添加索引

ALTER TABLE my_table ADD [UNIQUE] INDEX index_name(column_name);或者
CREATE INDEX index_name ON my_table(column_name);

刪除索引

DROP INDEX my_index ON tablename；

或者

ALTER TABLE table_name DROP INDEX index_name;

查看表中的索引

SHOW INDEX FROM tablename

查看查詢語句使用索引的情況

//explain 加查詢語句explain SELECT * FROM table_name WHERE column_1='123';

注意：

1、索引需要占用磁盤空間，因此在創建索引時要考慮到磁盤空間是否足夠

2、創建索引時需要對表加鎖，因此實際操作中需要在業務空閑期間進行

選擇一樣東西，就肯定有好有壞，我們說說索引的優缺點。

03

索引的優缺點

優勢：可以快速檢索，減少I/O次數，加快檢索速度；根據索引分組和排序，可以加快分組和排序；

劣勢：索引本身也是表，因此會占用存儲空間，一般來說，索引表占用的空間的數據表的1.5倍；索引表的維護和創建需要時間成本，這個成本隨著數據量增大而增大；構建索引會降低數據表的修改操作(刪除，添加，修改)的效率，因為在修改數據表的同時還需要修改索引表；

04

索引的實現原理

我們知道MySQL支持多種存儲引擎，而各種存儲引擎對索引的支持也各不相同，因此MySQL數據庫支持多種索引類型，如BTree索引，B+Tree索引，哈希索引，全文索引等等。

一、哈希索引

主要就是通過Hash算法(常見的Hash算法有直接定址法、平方取中法、折疊法、除數取余法、隨機數法)，將數據庫字段數據轉換成定長的Hash值，與這條數據的行指針一并存入Hash表的對應位置；如果發生Hash碰撞(兩個不同關鍵字的Hash值相同)，則在對應Hash鍵下以鏈表形式存儲。檢索算法：在檢索查詢時，就再次對待查關鍵字再次執行相同的Hash算法，得到Hash值，到對應Hash表對應位置取出數據即可，如果發生Hash碰撞，則需要在取值時進行篩選。目前使用Hash索引的數據庫并不多，主要有Memory等。MySQL目前有Memory引擎和NDB引擎支持Hash索引。

二、全文索引

????(1)全文索引也是MyISAM的一種特殊索引類型，主要用于全文索引，InnoDB從MYSQL5.6版本提供對全文索引的支持。

????(2)它用于替代效率較低的LIKE模糊匹配操作，而且可以通過多字段組合的全文索引一次性全模糊匹配多個字段。

????(3)同樣使用B-Tree存放索引數據，但使用的是特定的算法，將字段數據分割后再進行索引(一般每4個字節一次分割)，索引文件存儲的是分割前的索引字符串集合，與分割后的索引信息，對應Btree結構的節點存儲的是分割后的詞信息以及它在分割前的索引字符串集合中的位置。

三、B-Tree

????B-Tree是為磁盤等外存儲設備設計的一種平衡查找樹。

????系統從磁盤讀取數據到內存時是以磁盤塊(block)為基本單位的，位于同一個磁盤塊中的數據會被一次性讀取出來，而不是需要什么取什么。

????InnoDB 存儲引擎中有頁(Page)的概念，頁是其磁盤管理的最小單位。InnoDB 存儲引擎中默認每個頁的大小為16KB，可通過參數 innodb_page_size 將頁的大小設置為 4K、8K、16K，在 MySQL 中可通過如下命令查看頁的大小：show variables like 'innodb_page_size';

????而系統一個磁盤塊的存儲空間往往沒有這么大，因此 InnoDB 每次申請磁盤空間時都會是若干地址連續磁盤塊來達到頁的大小 16KB。InnoDB 在把磁盤數據讀入到磁盤時會以頁為基本單位，在查詢數據時如果一個頁中的每條數據都能有助于定位數據記錄的位置，這將會減少磁盤I/O次數，提高查詢效率。

????B-Tree 結構的數據可以讓系統高效的找到數據所在的磁盤塊。為了描述 B-Tree，首先定義一條記錄為一個二元組[key, data] ，key為記錄的鍵值，對應表中的主鍵值，data 為一行記錄中除主鍵外的數據。對于不同的記錄，key值互不相同。

一棵m階的B-Tree有如下特性：

每個節點最多有m個孩子

除了根節點和葉子節點外，其它每個節點至少有Ceil(m/2)個孩子。

若根節點不是葉子節點，則至少有2個孩子

所有葉子節點都在同一層，且不包含其它關鍵字信息

每個非終端節點包含n個關鍵字信息(P0,P1,…Pn, k1,…kn)

關鍵字的個數n滿足：ceil(m/2)-1 <= n <= m-1

ki(i=1,…n)為關鍵字，且關鍵字升序排序

Pi(i=1,…n)為指向子樹根節點的指針。P(i-1)指向的子樹的所有節點關鍵字均小于ki，但都大于k(i-1)

B-Tree 中的每個節點根據實際情況可以包含大量的關鍵字信息和分支，如下圖所示為一個 3 階的 B-Tree：

每個節點占用一個盤塊的磁盤空間，一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針，指針存儲的是子節點所在磁盤塊的地址。兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數據的范圍域。以根節點為例，關鍵字為17和35，P1指針指向的子樹的數據范圍為小于17，P2指針指向的子樹的數據范圍為17~35，P3指針指向的子樹的數據范圍為大于35。

模擬查找關鍵字29個過程：

根據根節點找到磁盤塊1，讀入內存。【磁盤I/O操作第1次】

比較關鍵字29在區間(17,35)，找到磁盤塊1的指針P2。

根據P2指針找到磁盤塊3，讀入內存。【磁盤I/O操作第2次】

比較關鍵字29在區間(26,30)，找到磁盤塊3的指針P2。

根據P2指針找到磁盤塊8，讀入內存。【磁盤I/O操作第3次】

在磁盤塊8中的關鍵字列表中找到關鍵字29。

分析上面過程，發現需要3次磁盤I/O操作，和3次內存查找操作。由于內存中的關鍵字是一個有序表結構，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。B-Tree相對于AVLTree縮減了節點個數，使每次磁盤I/O取到內存的數據都發揮了作用，從而提高了查詢效率。

四、B+Tree

B+Tree 是在 B-Tree 基礎上的一種優化，使其更適合實現外存儲索引結構，InnoDB 存儲引擎就是用 B+Tree 實現其索引結構。

從上一節中的B-Tree結構圖中可以看到每個節點中不僅包含數據的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數據較大時將會導致每個節點(即一個頁)能存儲的key的數量很小，當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。在B+Tree中，所有數據記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上只存儲key值信息，這樣可以大大加大每個節點存儲的key值數量，降低B+Tree的高度。

B+Tree相對于B-Tree有幾點不同：

非葉子節點只存儲鍵值信息；

所有葉子節點之間都有一個鏈指針；

數據記錄都存放在葉子節點中

將上一節中的B-Tree優化，由于B+Tree的非葉子節點只存儲鍵值信息，假設每個磁盤塊能存儲4個鍵值及指針信息，則變成B+Tree后其結構如下圖所示：

通常在B+Tree上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點，而且所有葉子節點(即數據節點)之間是一種鏈式環結構。因此可以對B+Tree進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節點開始，進行隨機查找。

可能上面例子中只有22條數據記錄，看不出B+Tree的優點，下面做一個推算：

InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT(占用4個字節)或BIGINT(占用8個字節)，指針類型也一般為4或8個字節，也就是說一個頁(B+Tree中的一個節點)中大概存儲16KB/(8B+8B)=1K個鍵值(因為是估值，為方便計算，這里的K取值為10^{3)。也就是說一個深度為3的B+Tree索引可以維護10}3 * 10^3 * 10^3 = 10億 條記錄。

實際情況中每個節點可能不能填充滿，因此在數據庫中，B+Tree的高度一般都在2-4層。MySQL的InnoDB存儲引擎在設計時是將根節點常駐內存的，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。

B+Tree性質

通過上面的分析，我們知道IO次數取決于b+數的高度h，假設當前數據表的數據為N，每個磁盤塊的數據項的數量是m，則有h=㏒(m+1)N，當數據量N一定的情況下，m越大，h越小；而m = 磁盤塊的大小 / 數據項的大小，磁盤塊的大小也就是一個數據頁的大小，是固定的，如果數據項占的空間越小，數據項的數量越多，樹的高度越低。這就是為什么每個數據項，即索引字段要盡量的小，比如int占4字節，要比bigint8字節少一半。這也是為什么b+樹要求把真實的數據放到葉子節點而不是內層節點，一旦放到內層節點，磁盤塊的數據項會大幅度下降，導致樹增高。當數據項等于1時將會退化成線性表。

當b+樹的數據項是復合的數據結構，比如(name,age,sex)的時候，b+數是按照從左到右的順序來建立搜索樹的，比如當(張三,20,F)這樣的數據來檢索的時候，b+樹會優先比較name來確定下一步的所搜方向，如果name相同再依次比較age和sex，最后得到檢索的數據；但當(20,F)這樣的沒有name的數據來的時候，b+樹就不知道下一步該查哪個節點，因為建立搜索樹的時候name就是第一個比較因子，必須要先根據name來搜索才能知道下一步去哪里查詢。比如當(張三,F)這樣的數據來檢索時，b+樹可以用name來指定搜索方向，但下一個字段age的缺失，所以只能把名字等于張三的數據都找到，然后再匹配性別是F的數據了， 這個是非常重要的性質，即索引的最左匹配特性。

后話

知道數據庫索引的原理更有利于我們表的設計，有利于提高數據庫SQL的編寫。這里只是簡單的介紹了數據庫的檢索原理。更多的其他數據庫檢索知識可以去尋找學習。

如果覺得好看，就贊一個吧~

往期精選

• PHP面試常考內容之Memcache和Redis(1)

• PHP面試常考內容之Memcache和Redis(2)

• PHP面試之面向對象(1)

• PHP面試常考內容之面向對象(2)

• PHP面試常考內容之面向對象(3)

如有疑問或想跟我交流，

可以加我的個人微信：leoyistar

關注琉憶編程庫，PHP面試資料都在這

點擊“好看”，就是對我最大的獎賞

總結

以上是生活随笔為你收集整理的rac一节点时间比另一个节点快_数据库数据那么多为什么可以检索这么快？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。