MySQL-06.索引的數據結構

1.為什麼使用索引

索引是存儲引擎用於快速找到數據記錄的一種數據結構，就好比一本書的目錄部分，通過目錄中找到對應文章的頁碼，便可快速定位到需要的文章。MySQL中的索引也是一樣的道理，進行數據查找時，首先查看查詢條件是否命中某條索引，符合則通過索引查找相關數據，如果不符合則需要全表掃描，即需要一條條的查找記錄，知道找到與條件符合的記錄。

上圖，是在沒有索引的情況下，從磁碟讀取數據的示意圖。建立索引的目的，就是為了減少磁碟I/O的次數，加快查詢速率。

2.索引及其優缺點

2.1 索引概述

MySQL官方對索引的定義為：索引(index)是幫助MySQL高效的獲取數據的數據結構。

索引的本質：索引是數據結構。可以簡單理解為排好序的快速查找數據結構，滿足特定查找演算法。這些數據結構以某種方式指向數據，這樣就可以在這些數據結構的基礎上實現高效查找演算法。

索引是在存儲引擎中實現的，因此每種存儲引擎的索引不一定完全相同，並且每種存儲引擎不一定支持所有索引類型。同時，存儲引擎可以定義每個表的最大索引數和最大索引長度。所有存儲引擎支持每個表至少16個索引，總索引長度至少為256位元組。有些存儲引擎支持更多的索引數和更大的索引長度。

2.2 優點

• 1.類似大學圖書館建數目索引，提高數據檢索的效率，降低資料庫磁碟的IO成本，這也是創建索引最主要的原因。
• 2.創建唯一索引，可以保證資料庫表中每一行數據的唯一性。
• 3.在實現數據的參考完整性方面，可以加速表與表之間的連接。換句話說，對於有依賴關係的子表和父表聯合查詢時，可以提高查詢速度。
• 4.在使用分組和排序子句進行數據查詢時，可以顯著減少查詢中分組和排序的時間，降低了CPU的消耗。

2.3 缺點

增加索引也有許多不利的方面，主要表現在以下幾個方面

• 1.創建索引和維護索引要耗費時間，並且隨著數據量的增加，所耗費的時間也會增加。
• 2.索引需要占磁碟空間，除了數據表占數據空間之外，每一個索引還要占一定的物理空間，存儲在磁碟上，如果有大量的索引，索引文件就可能比數據文件更快的達到最大文件尺寸。
• 3.雖然索引大大提高了查詢速度，同時卻會降低更新表的速度。當對錶中的數據進行增加，刪除和修改時，索引也要動態維護，這樣就降低了數據的維護速度。

因此，選擇使用索引時，需要總和考慮索引的優點和缺點。

提示:

索引可以提高查詢的速度,但是會影響插入記錄的速度.這種情況下,最優解就是,先移除索引,在插入數據完成後,再建立索引,用於查詢.

3.InnoDB中索引的推演

3.1 索引之前的查找

#準確匹配的例子
SELECT [列名列表] FROM 表名 WHERE 列名 = 'xxx';

3.1.1 在一個頁的查找

假設目前表的記錄比較少，所有的記錄都可以被存放到一個頁中，在查找記錄的時候可以根據搜索條件的不同分為兩種情況：

• 以主鍵為搜索條件

  可以在頁目錄中使用二分法快速定位到對應的槽，然後在遍歷該槽對應分組中的記錄即可快速找到指定的記錄。

• 以其他列作為搜索條件

​ 因為在數據頁中並沒有對非主鍵列建立所謂的頁目錄，所以無法通過二分法快速定位相應的槽。這種情況下只能從最小記錄開始依次遍歷單鏈表中的每條記錄，然後對比每條記錄是否符合搜索條件。很顯然這種查找的效率非常低。

3.1.2 在很多頁查找

大部分情況下我們表中存放的記錄都是非常多的，需要好多的數據頁來存儲這些記錄。在很多頁中查找記錄的話可以分為兩個步驟。

1.定位到記錄所在的頁。

2.從所在的頁中查找相應的數據。

在沒有索引的情況下，不論是根據主鍵列或者其他列的值進行查找，由於我們並不能快速的定位到記錄所在的頁，所有隻能從第一個頁沿著雙向鏈表一直往下找，在每一個頁中根據我們上面的查找方法去查找對應的記錄。因為要遍歷所有的數據頁，所以這種方式顯然是超級耗時的。如果一個表有一億條記錄呢？此時索引應運而生。

3.2 設計索引

建一張表

mysql> CREATE TABLE index_demo(
	-> 		c1 INT,
	->		c2 INT,
	->		c3 CHAR(1),
	->		PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact;

這個新建的表index_demo中有兩個int類型的列，一個CHAR(1)類型的列，而且c1列為主鍵，這個表使用Compact行格式來實際存儲記錄的。下圖，是簡化index_demo表的行格式圖：

• record_type：記錄頭信息的一項屬性，表示記錄的類型，0表示普通記錄，2表示最小記錄，3表示最大記錄，1暫時還沒用過，後面講。

• next_record：記錄頭信息的一些屬性，表示下一條記錄的地址相對於本記錄的地址偏移量，也可以簡單的理解為指向下一條記錄的指針。

• 各個列的值：這裡只記錄index_demo表中的三個列，c1，c2和c3。

• 其他信息：除了上述三種信息外的所有信息，包括其他隱藏列的值以及記錄的額外信息。

將記錄格式示意圖的其他信息暫時去掉並把它豎起來的效果如下圖

把一些記錄放到頁里的示意圖就是:

3.2.1 一個簡單的索引設計方案

我們在根據某個搜索條件查找一些記錄時為什麼要遍歷所有的數據頁呢？因為各個頁中的記錄並沒有規律，MySQL不知道搜索條件匹配那些記錄，所以不得不依次遍歷所有的數據頁。所以如果想快速定位到需要查找的記錄在那些數據頁怎麼辦？可以為快速定位記錄所在的數據頁建立一個目錄，建這個目錄必須滿足下邊這些要求。

• 下一個數據頁中記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值

假設：每個數據頁最多能存放3條記錄(實際上一個數據頁，可以存放很多條記錄)。

向index_demo表插入3條數據

mysql> insert into index_demo(c1,c2,c3) values(1,4,'u'),(3,9,'d'),(5,3,'y');
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

當下這些記錄按照主鍵大小串聯成一個單向鏈表，如圖所示

從圖中可以看出，index_demo表中的3條記錄都被插入到了編號為10(註意這個頁號，其實在底層存儲數據時，是一個具體的地址，比較好理解，抽象為頁號)的數據頁中。此時在插入一條記錄。

mysql> insert into index_demo(c1,c2,c3) values(4,4,'a');
Query OK, 1 row affected (0.00 sec)

因為假設一頁只能存放3條記錄，所以需要新增一個頁，用於保存c1=4的數據

註意，新分配的數據頁編號可能並不是連續的。它們只是通過維護者上一頁和下一頁的編號而建立了鏈表關係。另外，頁10中用戶記錄的最大的主鍵值是5，而頁28中有有一條記錄的主鍵值是4，因為5>4，所以這就不符合下一個頁的用戶數據的主鍵值必須大於上一個的用戶主鍵值(後一個頁的最主鍵最小值大於上一個頁的主鍵最大值)的要求，所以在插入主鍵值為4的記錄的時候需要伴隨著一次記錄移動，也就是把主鍵值為5的記錄移動到頁28中，然後再把主鍵為4的記錄插入到頁10中，這個過程的示意圖如下

這個過程表明瞭在對頁中記錄進行增刪改查操作的過程中，我們必須通過一些諸如記錄移動的操作來始終保證這個狀態一直成立：下一個頁的用戶數據的主鍵值必須大於上一個的用戶主鍵值。這個過程也被稱為頁分裂。

• 給所有的頁建立一個目錄項

由於數據頁的編號可能是不連續的，所以在向index_demo表中插入許多記錄後，可能是這樣的效果：

因為這些16KB的頁在物理存儲上是不連續的，所以如果想從這麼多頁中根據主鍵值快速定位某些記錄所在的頁，我們需要給這些頁建 立目錄，每個目錄項包括下邊兩個部分

1.頁的用戶記錄中最小的主鍵值，用key表示。

2.頁號，用page_no表示

為上邊幾個頁做好的目錄就行這樣

以頁28為例，它對應目錄項2，這個目錄項中包含著該頁的頁號28以及該頁中用戶記錄的最小主鍵值5。我們只需要把幾個目錄項在物理存儲器上連續存儲（比如：數組），就可以實現根據主鍵值快速查找某條記錄的功能了。

比如：查找主鍵值為20的記錄，具體查找過程分兩步：

1.先從目錄項中根據二分法快速確定出主鍵值為20的記錄在目錄項3中（因為12 < 20 <209），它對應的頁是頁9。

2.再根據前邊說的在頁中查找記錄的方式去頁9中定位具體的記錄。

至此，針對數據頁做的簡單目錄就搞定了。這個目錄有一個別名，稱為索引。

3.2.2 InnoDB中的索引方案

• (1) 迭代1次：目錄項記錄的頁

3.2.1小節稱為一個簡易的索引方案，是因為我們為了根據主鍵值進行查找時使用二分法快速定位具體的目錄項而假設所有的目錄項都可以在物理存儲器上連續存儲，但是這樣做，存在以下幾個問題

• 1.InnoDB是使用頁來作為管理存儲空間的基本單位，最多能保證16KB的連續存儲空間，而隨著表中記錄數量的增多，需要非常大的連續的存儲空間才能把所有的目錄項都放下，這對於記錄多的表，很顯然是不可能的。
• 2.回對錶中的數據進行增刪，假設把頁28中的記錄都刪除了，那意味著目錄項2也就沒有存在的必要了，這就需要把目錄項2後的目錄項都向前移動一下，這樣牽一發而動全身的操作效率是很差的。

所以，需要一種可以靈活管理所有目錄項的方式。我們發現目錄項其實和用戶記錄類似，只不過目錄項中的兩個列是主鍵和區號而已，為了和用戶記錄做區分，把這些用來表示目錄項的記錄稱為目錄項記錄。InnoDB區分一條記錄是普通的用戶記錄還是目錄項記錄。根據記錄頭信息record_type屬性

• 0：普通用戶數據
• 1：目錄項記錄
• 2：最小記錄
• 3：最大記錄

把上面，使用到的目錄項放到數據頁中的格式如下圖

從圖中可以看出來，我們新分配了一個編號為30的頁來專門存儲目錄項記錄。這裡再次強調目錄項記錄和普通的用戶記錄的

不同點：

• 目錄項記錄的record_type值是1，而普通用戶記錄的record_type值是0。
• 目錄項記錄只有主鍵值和頁的編號 兩個列，而普通的用戶記錄的列是用戶自己定義的，可能包含很多列，另外還有InnoDB自己添加的隱藏列。
• 瞭解：記錄頭信息里還有一個叫min_rec_mask的屬性，只有在存儲目錄項記錄的頁中的主鍵值最小的目錄項記錄的min_rec_mask值為1，其他別的記錄的min_rec_mask值都是0。

相同點：兩者用的是一樣的數據頁，都會為主鍵值生成Page Directory（頁目錄），從而在按照主鍵值進行查找時可以使用二分法來加快查詢速度。

現在以查找主鍵為 20 的記錄為例，根據某個主鍵值去查找記錄的步驟就可以大致拆分成下邊兩步：

1.先到存儲目錄項記錄的頁，也就是頁30中通過二分法快速定位到對應目錄項，因為12 < 20 <209，所以定位到對應的記錄所在的頁就是頁9。

2.再到存儲用戶記錄的頁9中根據二分法快速定位到主鍵值為20的用戶記錄。

• (2) 迭代2次：多個目錄項的頁
  
  從圖中可以看出，我們插入了一條主鍵值為320的用戶記錄之後需要兩個新的數據頁：

• 為存儲該用戶記錄而新生成了頁31。

• 因為原先存儲目錄項記錄的頁30的容量已滿（我們前邊假設只能存儲4條目錄項記錄），所以不得不需要一個新的頁32來存放頁31 對應的目錄項。

現在因為存儲目錄項記錄的頁不止一個，所以如果我們想根據主鍵值查找一條用戶記錄大致需要3個步驟，以查找主鍵值為20的記錄為例：

1.確定目錄項記錄頁

​ 我們現在的存儲目錄項記錄的頁有兩個，即頁30和頁32，又因為頁30表示的目錄項的主鍵值的範圍是[1, 320)，頁32表示的目錄項的主鍵值不小於320，所以主鍵值為20的記錄對應的目錄項記錄在頁30中。

2.通過目錄項記錄頁確定用戶記錄真實所在的頁。

​ 通過二分法，查找目錄記錄頁30中的數據，查找20所在的數據記錄頁為頁9。

3.在真實存儲用戶記錄的頁中定位到具體的記錄

• (3) 迭代3次：目錄項記錄頁的目錄頁

如圖，我們生成了一個存儲更高級目錄項的頁33，這個頁中的兩條記錄分別代表頁30和頁32，如果用戶記錄的主鍵值在 [1, 320) 之間，則到頁30中查找更詳細的目錄項記錄，如果主鍵值不小於320的話，就到頁32中查找更詳細的目錄項記錄。

我們可以用下邊這個圖來描述它：

這個數據結構，就是B+樹。

• (4) B+Tree

一個B+樹的節點其實可以分成好多層，規定最下邊的那層，也就是存放我們用戶記錄的那層為第0層，之後依次往上加。之前我們做了一個非常極端的假設：存放用戶記錄的頁最多存放3條記錄，存放目錄項記錄的頁最多存放4條記錄。其實真實環境中一個頁存放的記錄數量是非常大的，假設所有存放用戶記錄的葉子節點代表的數據頁可以存放100條用戶記錄，所有存放目錄項記錄的內節點代表的數據頁可以存放1000條目錄項記錄，那麼：

• 如果B+樹只有1層，也就是只有1個用於存放用戶記錄的節點，最多能存放100條記錄。
• 如果B+樹有2層，最多能存放1000×100=10,0000條記錄。
• 如果B+樹有3層，最多能存放1000×1000×100=1,0000,0000條記錄。
• 如果B+樹有4層，最多能存放1000×1000×1000×100=1000,0000,0000條記錄。相當多的記錄！！！

你的表裡能存放100000000000條記錄嗎？所以一般情況下，我們用到的B+樹都不會超過4層，那我們通過主鍵值去查找某條記錄最多只需要做4個頁面內的查找（查找3個目錄項頁和一個用戶記錄頁），又因為在每個頁面內有所謂的Page Directory（頁目錄），所以在頁面內也可以通過二分法實現快速定位記錄。

註意，上述所考慮的情況是，精確查找，也就是查找一個條件，而不是一個範圍的查詢語句。

3.3 常見索引概念

索引按照物理實現方式，索引可以分為2種，聚簇(聚集，也叫主鍵索引)和非聚簇(非聚集)索引。我們也把非聚集索引稱為二級索引或者輔助索引。

3.3.1 聚簇索引

聚簇索引並不是一種單獨的索引類型，而是一種數據存儲方式(當前表的所有數據都存儲在葉子節點)，也就是索引即數據，數據即索引。

術語 "聚簇"表示數據行和相鄰的鍵值聚簇的存儲在一起。

特點：

• 1.使用記錄主鍵值的大小進行記錄和頁的排序
  • 頁內的記錄是按照主鍵的大小順序排成一個單向鏈表。
  • 各個存放用戶記錄的頁也是根據頁中用戶記錄的主鍵大小順序拍成一個雙向鏈表。
  • 存放目錄項記錄的頁分為不同層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表。
• 2.B+樹的葉子節點存儲的是完整的用戶記錄
  • 所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值(包括隱藏列)。

具有這兩種特性的B+樹稱為聚簇索引，所有完整的用戶記錄都存放在這個聚簇索引的葉子節點。這種聚簇索引並不需要在MySQL語句中使用INDEX語句去創建，InnoDB存儲引擎會自動創建聚簇索引。

優點：

• 數據訪問更快，因為聚簇索引將索引和數據保存在同一個B+樹中，因此從聚簇索引中獲取數據比非聚簇索引更快。

• 聚簇索引對於主鍵的排序查找和範圍查找速度非常快。

• 按照聚簇索引排列順序，查詢顯示一定範圍數據的時候，由於數據都是緊密相連，資料庫不用從多個數據塊中提取數據，所以節省了大量的io操作。

缺點：

• 插入速度嚴重依賴於插入順序，按照主鍵的順序插入是最快的方式，否則將會出現頁分裂，嚴重影響性能。因此，對於InnoDB表，一般都會定義一個自增的ID列為主鍵。

• 更新主鍵的代價很高，因為將會導致被更新的行移動。因此，對於InnoDB表，我們一般定義主鍵為不可更新。

• 二級索引訪問需要兩次索引查找，第一次找到主鍵值，第二次根據主鍵值找到行數據

限制：

• 對於MySQL資料庫目前只有InnoDB存儲引擎支持聚簇索引，而MyISAM並不支持聚簇索引(MyISAM底層存儲文件是表名.MYI和表名.MYD，索引和數據分開存儲的)。

• 由於數據物理存儲排序方式只能有一種，所以每個MySQL的表只能有一個聚簇索引。一般情況下就是該表的主鍵。

• 如果沒定義主鍵，InnoDB會選擇非空的唯一列代替。如果沒有這樣的索引，InnoDB會隱式的定義一個主鍵來作為聚簇索引。

• 為了充分利用聚簇索引的聚簇的特性，所以InnoDB表的主鍵列儘量選用有序的順序id，而不建議用無序的id，比如UUID，MD5，HASH，等作為主鍵，無法保證數據的順序增長。

3.3.2 二級索引(輔助索引，非聚簇索引)

上邊介紹的聚簇索引只能在搜索條件是主鍵值時才能發揮作用，因為B+樹的數據都是按照主鍵進行排序的。那如果我們想以別的列作為搜索條件怎麼辦？

答案：可以多建立幾棵B+樹，不同的B+樹中的數據採用不同的排序規則。比方說我們用index_demo表的c2列作為數據頁，頁中記錄的排序規則，,再建一棵B+樹，效果如下圖所示。

這個B+樹，和聚簇索引有幾處不同：

• 使用記錄中的c2列的大小進行記錄和頁的排序，這包括三個方面的含義：

  • 頁內的記錄都是按照c2列的大小順序排成一個單向列表。
  • 各個存放用戶記錄的頁也是根據頁中記錄的c2列大小順序排成一個雙向列表。
  • 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的c2列大小排序排成一個雙向鏈表。

• B+樹的葉子節點存儲的不是完整的用戶記錄，而只是c2列+主鍵這兩個列的值。

• 目錄項記錄中不再是主鍵+頁號的搭配，而是c2列+頁號的搭配。

所以，如果使用c2列構建的B+樹，用以數據的查詢，以c2等於4的記錄為例

1.確定目錄項記錄頁，根據根頁面，也就是頁44，可以快速定位目錄項記錄所在的頁42（2 < 4 < 9）

2.通過目錄下記錄頁確定用戶記錄真實所在的頁，在頁42中可以快速定位到實際存儲用戶記錄的頁，但是由於c2列並沒有唯一性約束，所以c2等於4的記錄可能分佈在多個數據頁，2 < 4 <=4，所以確定實際存儲用戶記錄的頁在頁34和頁35中。

3.在真實存儲用戶記錄的頁中定位到具體的記錄。

4.但是當前樹，只存儲了c2和c1列的數據，所以必須再根據主鍵值去聚簇索引中再查找一邊完整的用戶記錄。(這個過程，就稱為回表)

概念：回表 我們根據這個以c2列大小排序的B+樹只能確定我們要查找記錄的主鍵值，所以如果我們想根據c2列的值查找到完整的用戶記錄的話，仍然需要到聚簇索引中再查一遍，這個過程稱為回表。也就是根據c2列的值查詢一條完整的用戶記錄需要使用到2棵B+樹！

問題：為什麼還需要再一次回表操作呢？直接把完整的用戶記錄放到葉子節點不行嗎？

答案

如果把完整的用戶記錄放到葉子節點是可以不用回表了，但是很占地方，相當於每一個索引樹中，都存儲了當前表的完整記錄，浪費存儲空間。

這種非主鍵列建立的B+樹需要一次回表操作才可以定位到完整的用戶記錄，所以這種B+樹被稱為二級索引，或者輔助索引。由於我們使用的是c2列的作為B+樹的排序規則，所以也稱這個B+樹是為c2列建立的索引。

非聚簇索引的存在不影響數據在聚簇索引中的組織，所以一張表可以有多個非聚簇索引。

結：聚簇索引和非聚簇索引的原理不同，在使用上也有一些區別

1.聚簇索引的葉子節點存儲的就是我們的數據記錄，非聚簇索引的葉子節點存儲的是數據位置。非聚簇索引不會影響數據表的物理存儲順序。

2.一個表只能有一個聚簇索引，因為只能有一種排序存儲的方式，但可以有多個非聚簇索引，也就是多個索引目錄提高數據檢索。

3.使用聚簇索引的時候，數據的查詢效率高，但如果對數據進行插入，刪除，更新操作效率，比非聚簇索引，效率低。

3.3.3 聯合索引

我們也可以同時以多個列的大小作為排序規則，也就是同時為多個列建立索引，比方說我們想讓B+樹按照c2和c3列的大小進行排序，這個包含兩層含義：

• 先把各個記錄和頁按照c2列進行排序。
• 在記錄的c2列相同的情況下，採用c3列進行排序。

如圖所示，我們需要註意以下幾點：

• 每條目錄項記錄都由c2,c3,頁號這三部分組成，各條記錄先按照c2列的值進行排序，如果記錄的c2列相同，則按照c3列進行排序。
• B+樹葉子節點的記錄，由c2,c3,主鍵c1列組成。

註意點，以c2和c3列的大小為排序規則建立的B+樹稱為聯合索引，本質上也是一個二級索引。它的意思與分別為c2和c3列分別建立索引的表述是不同的，不同點如下：

• 建立聯合索引只會建立如上圖一樣的1棵B+樹。
• 為c2和c3列分別建立索引會分別以c2和c3列的大小為排序規則建立2棵B+樹。

3.4 InnoDB的B+樹索引的註意事項

3.4.1 根頁面位置萬年不動

我們前邊介紹B+樹索引的時候，為了大家理解上的方便，先把存儲用戶記錄的葉子節點都畫出來，然後接著畫存儲目錄項記錄的內節點，實際上B+樹的形成過程是這樣的:

• 每當為某個表創建一個B+樹索引(聚簇索引不是人為創建的，預設就有）的時候，都會為這個索引創建一個根節點頁面。最開始表中沒有數據的時候，每個B+樹索引對應的根節點中既沒有用戶記錄，也沒有目錄項記錄。
• 隨後向表中插入用戶記錄時，先把用戶記錄存儲到這個根節點中。
• 當根節點中的可用空間用完時繼續插入記錄，此時會將根節點中的所有記錄複製到一個新分配的頁，比如頁a中，然後對這個新頁進行頁分裂的操作，得到另一個新頁，比如頁b。這時新插入的記錄根據鍵值（也就是聚簇索引中的主鍵值，二級索引中對應的索引列的值)的大小就會被分配到頁a或者b中，而根節點便升級為存儲目錄項記錄的頁。

這個過程特別註意的是:一個B+樹索引的根節點自誕生之日起，便不會再移動。這樣只要我們對某個表建立一個索引，那麼它的根節點的頁號便會被記錄到某個地方，然後凡是InnoDB存儲引擎需要用到這個索引的時候，都會從那個固定的地方取出根節點的頁號，從而來訪問這個索引。

3.4.2 內節點(非葉子)中目錄項記錄的唯一性

我們知道B+樹索引的內節點中目錄項記錄的內容是索引列＋頁號的搭配，但是這個搭配對於二級索引來說有點兒不嚴謹。還拿index_demd表為例，假設這個表中的數據是這樣的:

如果二級索引中目錄項記錄的內容只是索引列+列號的搭配的話，那麼為c2列建立索引後的B+樹應該長這樣：

如果想新插入一行記錄，其中c1、c2、c3的值分別是9、1、'c'，那麼在修改這個為c2列建立的二級索引對應的B+樹時便碰到了個大問題：由於頁3中存儲的目錄項記錄是由c2列＋頁號的值構成的，頁3中的兩條目錄項記錄對應的c2列的值都是1，而新插入的這條記錄的c2列的值也是1，那我們這條新插入的記錄到底應該放到頁4中，還是應該放到頁5中啊? 答案是:對不起，懵了。

為了讓新插入記錄能找到自己在那個頁里，我們需要保證在B+樹的同一層內節點的目錄項記錄，除頁號這個欄位以外是唯一的。所以對於二級索引的內節點的目錄項記錄的內容實際上是由三個部分構成的:

• 索引列的值

• 主鍵值

• 頁號

也就是我們把主鍵值也添加到二級索引內節點中的目錄項記錄了，這樣就能保證B+樹每一層節點中各條目錄項記錄除頁號這個欄位外是唯一的，所以我們為c2列建立二級索引後的示意圖實際上應該是這樣子的:

這樣我們再插入記錄(9，1， 'c')時，由於頁3中存儲的目錄項記錄是由c2列＋主鍵＋頁號的值構成的，可以先把新記錄的c2列的值和頁3中各目錄項記錄的c2列的值作比較，如果c2列的值相同的話，可以接著比較主鍵值，因為B+樹同一層中不同目錄項記錄的c2列＋主鍵的值肯定是不一樣的，所以最後肯定能定位唯一的一條目錄項記錄，在本例中最後確定新記錄應該被插入到頁5中。

3.4.3 一個頁面最少存儲2條記錄

一個B+樹只需要很少的層級就可以輕鬆存儲數億條記錄，查詢速度相當不錯！這是因為B+樹本質上就是一個大的多層級目錄，每經過一個目錄時都會過濾掉許多無效的子目錄，直到最後訪問到存儲真實數據的目錄。那如果一個大的目錄中只存放一個子目錄是個啥效果呢?那就是目錄層級非常非常非常多，而且最後的那個存放真實數據的目錄中只能存放一條記錄。費了半天勁只能存放一條真實的用戶記錄?所以InnoDB的一個數據頁至少可以存放兩條記錄。

4.MyISAM中的索引方案

4.1 概述

B樹索引適用存儲引擎如表所示

即使多個存儲引擎支持同一種類型的索引，但是他們的實現原理也是不同的。Innodb和MylSAM預設的索引是Btree索引；而Memory認的索引是Hash索引。

MylISAM引擎使用B+Tree作為索引結構，葉子節點的data域存放的是數據記錄的地址。

4.2 MyISAM索引原理

下圖是MylSAM索引的原理圖。

我們知道InnoDB中索引即數據，也就是聚簇索引的那棵B+樹的葉子節點中已經把所有完整的用戶記錄都包含了，而MyISAM的索引方案雖然也使用樹形結構，但是卻將索引和數據分開存儲:

• 將表中的記錄按照記錄的插入順序單獨存儲在一個文件中，稱之為數據文件。這個文件並不劃分為若幹個數據頁，有多少記錄就往這個文件中塞多少記錄就成了。由於在插入數據的時候並沒有刻意按照主鍵大小排序，所以我們並不能在這些數據上使用二分法進行查找。

• 使用MyISAM存儲引擎的表會把索引信息另外存儲到一個稱為索引文件的另一個文件中。MyISAM會單獨為表的主鍵創建一個索引，只不過在索引的葉子節點中存儲的不是完整的用戶記錄，而是主鍵值＋數據記錄地址的組合。

這裡設表-共有三列, 假設我們以Col1為主鍵，上圖是一 個MyISAM表的主索引 (Primarykey) 示意。可以看出MyISAM的索引文件僅僅保存數據記錄的地址。在MyISAM中， 主鍵索引和二級索引(Secondary key)在結構上沒有任何區別，只是主鍵索引|要求key是唯一的， 而二級索引的key可以重覆。如果我們在Col2上建立一個二級索引，則此索引的結構如下圖所示:

同樣也是一棵B+Tree，data域保存數據記錄的地址。因此，MyISAM中索引檢索的演算法為：首先按照B+Tree搜索演算法搜索索引，如果指定的Key存在，則取出其data域的值，然後以data域的值為地址，讀取相應數據記錄。

4.3 MyISAM與InnoDB區別

MyISAM的索引方式都是“非聚簇"的，與InnoDB包含1個聚簇索引是不同的。小結兩種引擎中索引的區別:
①在InnoDB存儲引擎中，我們只需要根據主鍵值對聚簇索引進行一次查找就能找到對應的記錄，而在MyISAM中卻需要進行一次回表操作，意味著MylSAM中建立的索引相當於全部都是二級索引。

② InnoDB的數據文件本身就是索引文件，而MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。

③ InnoDB的非聚簇索引data域存儲相應記錄主鍵的值，而MyISAM索引記錄的是地址。換句話說，InnoDB的所有非聚簇索引都引用主鍵作為data域。

④ MyISAM的回表操作是十分快速的，因為是拿著地址偏移量直接到文件中取數據的，反觀InnoDB是通過獲取主鍵之後再去聚簇索引里找記錄，雖然說也不慢，但還是比不上直接用地址去訪問。

⑤InnoDB要求表必須有主鍵 （MyISAM可以沒有）。如果沒有顯式指定，則MySQL系統會自動選擇一個可以非空且唯一標識數據記錄的列作為主鍵。如果不存在這種列，則MysQL自動為InnoDB表生成一個隱含欄位作為主鍵，這個欄位長度為6個位元組，類型為長整型。

小結:
瞭解不同存儲引擎的索引實現方式對於正確使用和優化索引都非常有幫助。比如:

舉例1:知道了innoDB的索引實現後，就很容易明白為什麼不建議使用過長的欄位作為主鍵，因為所有二級索引都引用主鍵索引，過長的主鍵索引會令二級索引變得過大。

舉例2:用非單調的欄位作為主鍵在InnoDB中不是個好主意，因為InnoDB數據文件本身是一棵B+Tree，非單調的主鍵會造成在插入新記錄時，數據文件為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增欄位作為主鍵則是一個很好的選擇。

5.索引的代價

索引是個好東西，可不能亂建，它在空間和時間上都會有消耗：

• 空間上的代價

每建立一個索引都要為它建立一棵B+樹，每一棵B+樹的每一個節點都是一個數據頁，一個頁預設會占用16KB的存儲空間，一棵很大的B+樹由許多數據頁組成，那就是很大的一片存儲空間。

• 時間上的代價

每次對錶中的數據進行增、刪、改操作時，都需要去修改各個B+樹索引。而且我們講過，B+樹每層節點都是按照索引列的值從小到大的順序排序而組成了雙向鏈表。不論是葉子節點中的記錄，還是內節點中的記錄（也就是不論是用戶記錄還是目錄項記錄）都是按照索引列的值從小到大的順序而形成了一個單向鏈表。而增、刪、改操作可能會對節點和記錄的排序造成破壞，所以存儲引擎需要額外的時間進行一些記錄移位、頁面分裂、頁面回收等操作來維護好節點和記錄的排序。如果我們建了許多索引，每個索引對應的B+樹都要進行相關的維護操作，會給性能拖後腿。

一個表的索引建的越多，就會占用越多的存儲空間，在增刪記錄的時候性能就越差。為了能建立又好又少的索引，需要學習索引在那些條件下起作用。

6.MySQL索引數據結構選擇的合理性

從MysQL的角度講，不得不考慮一個現實問題就是磁碟IO。如果我們能讓索引的數據結構儘量減少硬碟的I/O操作，所消耗的時間也就越小。可以說，磁碟的I/O操作次數對索引的使用效率至關重要。

查找都是索引操作，一般來說索引非常大，尤其是關係型資料庫，當數據量比較大的時候，索引的大小有可能幾個G甚至更多，為了減少索引在記憶體的占用，資料庫索引是存儲在外部磁碟上的。當我們利用索引查詢的時候，不可能把整個索引全部載入到記憶體，只能逐一載入，那麼MySQL衡量查詢效率的標準就是磁碟IO次數。

6.1 全表遍歷

就是順序從磁碟讀取表的數據，進行判斷是否相等。

6.2 Hash結構

Hash本身是一個函數，又被稱為散列函數，它可以幫助我們大幅提升檢索數據的效率。

Hash演算法是通過某種確定性的演算法（比如MD5、SHA1、SHA2、SHA3）將輸入轉變為輸出。相同的輸入永遠可以得到相同的輸出，假設輸入內容有微小偏差，在輸出中通常會有不同的結果。

舉例:如果你想要驗證兩個文件是否相同，那麼你不需要把兩份文件直接拿來比對，只需要讓對方把Hash函數計算得到的結果告訴你即可，然後在本地同樣對文件進行Hash 函數的運算，最後通過比較這兩個Hash 函數的結果是否相同，就可以知道這兩個文件是否相同。

加速查找速度的數據結構，常見的有兩類

1.樹，例如平衡二叉樹，查詢/插入/修改/刪除的平均時間複雜度都是O(log2N);

2.哈希，例如HashMap，查詢/插入/修改/刪除的平均時間複雜度都是O(1);

採用Hash進行檢索效率非常高，基本上一次檢索就可以找到數據，而B+樹需要自頂向下依次查找，多次訪問節點才能找到數據，中間需要多次I/O操作，從效率來說 Hash 比 B+樹更快。

在哈希的方式下，一個元素k處於h(k)中，即利用哈希函數h，根據關鍵字k計算出槽的位置。函數h將關鍵字域映射到哈希表T[0...m-1]的槽位上。

上圖中哈希函數h有可能將兩個不同的關鍵字映射到相同的位置，這叫做碰撞，在資料庫中一般採用鏈接法來解決。在鏈接法中，將散列到同一槽位的元素放在一個鏈表中，如下圖所示：

實驗：體會數組和hash表的查找方面的效率區別

//演算法時間複雜度O(n) 遍歷方式
@Test
public void test1(){
    int[] arr = new int[100000];
    for(int i = 0;i < arr.length;i++){
    	arr[i] = i + 1;
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000;j++){
        int temp = j;
        for(int i = 0;i < arr.length;i++){
            if(temp == arr[i]){
                break;
            }	
        }
    }
    long end = System.currentTimeMillis();
    System.out.println("time： " + (end - start)); //time： 823
}

//演算法複雜度為 O(1)
@Test
public void test2(){
    HashSet<Integer> set = new HashSet<>(100000);
    for(int i = 0;i < 100000;i++){
    	set.add(i + 1);
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000;j++) {
        int temp = j;
        boolean contains = set.contains(temp);
    }
    long end = System.currentTimeMillis();
    System.out.println("time： " + (end - start)); //time： 5
}

Hash結構效率高，那為什麼索引結構要設計成樹型呢？

原因1: Hash索引僅能滿足(=) (<>)和IN查詢。如果進行範圍查詢，哈希型的索引，時間複雜度會退化為O(n);而樹型的“有序”特性，依然能夠保持O(log2N)的高效率。

原因2: Hash索引還有一個缺陷，數據的存儲是沒有順序的，在ORDER BY的情況下，使用Hash索引還需要對數據重新排序。

原因3:對於聯合索引的情況，Hash值是將聯合索引鍵合併後一起來計算的，無法對單獨的一個鍵或者幾個索引鍵進行查詢。

原因4:對於等值查詢來說，通常Hash索引的效率更高，不過也存在一種情況，就是索引列的重覆值如果很多，效率就會降低。這是因為遇到 Hash衝突時，需要遍歷桶中的行指針來進行比較，找到查詢的關鍵字非常耗時。所以，Hash索引通常不會用到重覆值多的列上，比如列為性別、年齡的情況等。

Hash索引適用存儲引擎如表所示：

Hash索引的適用性：

Hash索引存在著很多限制，相比之下在資料庫中B+樹索引的使用面會更廣，不過也有一些場景採用Hash索引效率更高，比如在鍵值型(Key-Value)資料庫中,Redis存儲的核心就是Hash表。

MySQL中的Memory存儲引擎支持Hash存儲，如果我們需要用到查詢的臨時表時，就可以選擇Memory存儲引擎，把某個欄位設置為Hash 索引，比如字元串類型的欄位，進行Hash計算之後長度可以縮短到幾個位元組。當欄位的重覆度低，而且經常需要進行等值查詢的時候，採用Hash索引是個不錯的選擇。

另外，InnoDB本身不支持Hash 索引，但是提供自適應Hash 索引(Adaptive Hash Ilndex)。什麼情況下才會使用自適應Hash索引呢?如果某個數據經常被訪問，當滿足一定條件的時候，就會將這個數據頁的地址存放到Hash表中。這樣下次查詢的時候，就可以直接找到這個頁面的所在位置。這樣讓B+樹也具備了Hash索引的優點。

採用自適應 Hash 索引目的是方便根據 SQL 的查詢條件加速定位到葉子節點，特別是當 B+ 樹比較深的時候，通過自適應 Hash 索引可以明顯提高數據的檢索效率。

我們可以通過innodb_adaptive_hash_index變數來查看是否開啟了自適應 Hash，比如：

mysql> show variables like '%adaptive_hash_index';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| innodb_adaptive_hash_index | ON    |
+----------------------------+-------+
1 row in set (0.01 sec)

6.3 二叉搜索樹

如果我們利用二叉樹作為索引結構，那麼磁碟的IO次數和索引樹的高度是相關的。
1.二叉搜索樹的特點

• 一個節點只能有兩個子節點，也就是一個節點度不能超過2。
• 左子節點<本節點;右子節點>=本節點，比我大的向右，比我小的向左

2.查找規則

我們先來看下最基礎的二叉搜索樹(Binary Search Tree)，搜索某個節點和插入節點的規則一樣我們假設搜索插入的數值為key:

1.如果key大於根節點，則在右子樹中進行查找;

2.如果key小於根節點，則在左子樹中進行查找;

3.如果key等於根節點，也就是找到了這個節點，返回根節點即可。

舉個例子，我們對數列(34，22，89，5，23，77，91）創造出來的二分查找樹如下圖所示:

但是存在特殊的情況，就是有時候二叉樹的深度非常大。比如我們給出的數據順序是(5, 22,23,34,77,89,91)，創造出來的二分搜索樹如下圖所示:

上面第二棵樹也屬於二分查找樹，但是性能上已經退化成了一條鏈表，查找數據的時間複雜度變成O(n)。能看出來第一個樹的深度是3，也就是說最多只需3次比較，就可以找到節點，而第二個樹的深度是7，最多需要7次比較才能找到節點。為了提高查詢效率，就需要減少磁碟IO數。為了減少磁碟lO的次數，就需要儘量降低樹的高度，需要把原來“瘦高”的樹結構變的“矮胖”，樹的每層的分叉越多越好。

6.4 AVL樹

為瞭解決上面二叉查找樹退化成鏈表的問題，人們提出了平衡二叉搜索樹(Balanced Binary Tree)，又稱為AVL樹(有別於AVL演算法)，它在二叉搜索樹的基礎上增加了約束，具有以下性質:

它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。

這裡說一下，常見的平衡二叉樹有很多種，包括了平衡二叉搜索樹、紅黑樹、數堆、伸展樹。平衡二叉搜索樹是最早提出來的自平衡二叉搜索樹，當我們提到平衡二叉樹時一般指的就是平衡二叉搜索樹。事實上，第一棵樹就屬於平衡二叉搜索樹，搜索時間複雜度就是O( log2n)。

數據查詢的時間主要依賴於磁碟IO的次數，如果我們採用二叉樹的形式，即使通過平衡二叉搜索樹進行了改進，樹的深度也是O(log2n)，當n 比較大時，深度也是比較高的，比如下圖的情況:

每訪問一次節點就需要進行一次磁碟I/0操作，對於上面的樹來說，我們需要進行5次I/O操作。雖然平衡二叉樹的效率高，但是樹的深度也同樣高，這就意味著磁碟I/О操作次數多，會影響整體數據查詢的效率。

針對同樣的數據，如果我們把二叉樹改成M叉樹(M>2）呢?當M=3時，同樣的31個節點可以由下麵的三叉樹來進行存儲:

你能看到此時樹的高度降低了，當數據量N大的時候，以及樹的分叉數M大的時候，M叉樹的高度會遠小於二叉樹的高度(M >2)。所以，我們需要把樹從“瘦高"變“矮胖”。

6.5 B-Tree

B樹的英文是Balance Tree，也就是多路平衡查找樹。簡寫為B-Tree(註意橫杠表示這兩個單詞連起來的意思，不是減號)。它的高度遠小於平衡二叉樹的高度。

B樹的結構如下圖所示:

B樹作為多路平衡查找樹，它的每一個節點最多可以包括M個子節點，M稱為B樹的階。每個磁碟塊中包括了關鍵字和子節點的指針。如果一個磁碟塊中包括了x個關鍵字，那麼指針數就是x+1。對於一個100階的B樹來說，如果有3層的話最多可以存儲約100萬的索引數據。對於大量的索引數據來說，採用B樹的結構是非常適合的，因為樹的高度要遠小於二叉樹的高度。

一個 M 階的 B 樹（M>2）有以下的特性：

1. 根節點的兒子數的範圍是 [2,M]。

2. 每個中間節點包含 k-1 個關鍵字和 k 個孩子，孩子的數量 = 關鍵字的數量 +1，k 的取值範圍為[ceil(M/2), M]。

3. 葉子節點包括 k-1 個關鍵字（葉子節點沒有孩子），k 的取值範圍為 [ceil(M/2), M]。

4. 假設中間節點節點的關鍵字為：Key[1], Key[2], …, Key[k-1]，且關鍵字按照升序排序，即 Key[i]<Key[i+1]。此時 k-1 個關鍵字相當於劃分了 k 個範圍，也就是對應著 k 個指針，即為：P[1], P[2], …,P[k]，其中 P[1] 指向關鍵字小於 Key[1] 的子樹，P[i] 指向關鍵字屬於 (Key[i-1], Key[i]) 的子樹，P[k]指向關鍵字大於 Key[k-1] 的子樹。

5. 所有葉子節點位於同一層。

上面那張圖所表示的 B 樹就是一棵 3 階的 B 樹。我們可以看下磁碟塊 2，裡面的關鍵字為（8，12），它有 3 個孩子 (3，5)，(9，10) 和 (13，15)，你能看到 (3，5) 小於 8，(9，10) 在 8 和 12 之間，而 (13，15)大於 12，剛好符合剛纔我們給出的特征。

然後我們來看下如何用 B 樹進行查找。假設我們想要查找的關鍵字是 9，那麼步驟可以分為以下幾步：

1. 我們與根節點的關鍵字 (17，35）進行比較，9 小於 17 那麼得到指針 P1；
2. 按照指針 P1 找到磁碟塊 2，關鍵字為（8，12），因為 9 在 8 和 12 之間，所以我們得到指針 P2；
3. 按照指針 P2 找到磁碟塊 6，關鍵字為（9，10），然後我們找到了關鍵字 9。

你能看出來在 B 樹的搜索過程中，我們比較的次數並不少，但如果把數據讀取出來然後在記憶體中進行比較，這個時間就是可以忽略不計的。而讀取磁碟塊本身需要進行 I/O 操作，消耗的時間比在記憶體中進行比較所需要的時間要多，是數據查找用時的重要因素。B 樹相比於平衡二叉樹來說磁碟 I/O 操作要少，在數據查詢中比平衡二叉樹效率要高。所以只要樹的高度足夠低，IO次數足夠少，就可以提高查詢性能。

小結:

1.B樹在插入和刪除節點的時候如果導致樹不平衡，就通過自動調整節點的位置來保持樹的自平衡。

2.關鍵字集合分佈在整棵樹中,即葉子節點和非葉子節點都存放數據。搜索有可能在非葉子節點結束

3.其搜索性能等價於在關鍵字全集內做一次二分查找。
舉例

6.6 B+Tree

B+樹也是一種多路搜索樹，基於B樹進行了改進，主流的DBMS都支持B+樹的索引方式，比如MySQL。相比與B-Tree，B+Tree適合文件索引系統。

• MySQL官網說明
  
  B+樹和B樹的差異：
  1.有 k 個孩子的節點就有 k 個關鍵字。也就是孩子數量 = 關鍵字數，而 B 樹中，孩子數量 = 關鍵字數+1。

2.非葉子節點的關鍵字也會同時存在在子節點中，並且是在子節點中所有關鍵字的最大（或最小）。

3.非葉子節點僅用於索引，不保存數據記錄，跟記錄有關的信息都放在葉子節點中。而 B 樹中，非葉子節點既保存索引，也保存數據記錄。

4.所有關鍵字都在葉子節點出現，葉子節點構成一個有序鏈表，而且葉子節點本身按照關鍵字的大小從小到大順序鏈接。

B 樹和 B+ 樹都可以作為索引的數據結構，在 MySQL 中採用的是 B+ 樹。

但B樹和B+樹各有自己的應用場景，不能說B+樹完全比B樹好，反之亦然。

思考題：為了減少IO，索引樹會一次性載入嗎？

1、資料庫索引是存儲在磁碟上的，如果數據量很大，必然導致索引的大小也會很大，超過幾個G。
2、當我們利用索引查詢時候，是不可能將全部幾個G的索引都載入進記憶體的，只能是逐一載入每一個磁碟頁，因為磁碟頁對應著索引樹的節點。

思考題：B+樹的存儲能力如何？為何說一般查找行記錄，最多只需1~3次磁碟IO

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億條記錄。(這裡假定一個數據頁也存儲10^3條行記錄數據了)

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

思考題：為什麼說B+樹比B-樹更適合實際應用中操作系統的文件索引和資料庫索引？

1、B+樹的磁碟讀寫代價更低
B+樹的內部結點並沒有指向關鍵字具體信息的指針。因此其內部結點相對B樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。

2、B+樹的查詢效率更加穩定
由於非終結點並不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。

思考題：Hash索引與 B+ 樹索引的區別

Hash索引結構和B+樹的不同，因此在索引使用上也會有差別

1、Hash索引不能進行範圍查詢，而B+樹可以。這是因為Hash索引指向的數據是無序的，而B樹的葉子節點是個有序的鏈表。
2、Hash索引不支持聯合索引的最左側原則(即聯合索引的部分索引無法使用)，而B樹可以。對於聯合索引來說，Hash索引在計算Hash值的時候是將索引鍵合併後再一起計算Hash值，所以不會針對每個索引單獨計算Hash值。因此如果用到聯合索引的一個或者幾個索引時，聯合索引無法被利用。
3、Hash索引不支持 ORDER BY 排序，因為Hash索引指向的數據是無序的，因此無法起到排序優化的作用，而B+樹索引數據是有序的，可以起到對該欄位ORDER BY排序優化的作用。同理，我們也無法用Hash索引進行模糊查詢，而B+樹使用LIKE進行模糊查詢的時候，LIKE後面後模糊查詢（比如%結尾）的話就可以起到優化作用。

4.InnoDB不支持哈希索引
思考題：Hash索引與B+樹索引是在建索引的時候手動指定的嗎？
如果使用的是MySQL的話，我們需要瞭解MySQL的存儲引擎都支持哪些索引結構，如下圖所示。

能看到，針對InnoDB和MylISAM存儲引擎，都會預設採用B+樹索引，無法使用Hash索引。InnoDB提供的自適應Hash是不需要手動指定的。如果是Memory/Heap和NDB存儲引擎，是可以進行選擇Hash索引的。|

6.7 R樹

R-Tree在MySQL很少使用，僅支持geometry數據類型，支持該類型的存儲引擎只有myisam、bdb、innodb、ndb、archive幾種。舉個R樹在現實領域中能夠解決的例子：查找20英里以內所有的餐廳。如果沒有R樹你會怎麼解決？一般情況下我們會把餐廳的坐標(x,y)分為兩個欄位存放在資料庫中，一個欄位記錄經度，另一個欄位記錄緯度。這樣的話我們就需要遍歷所有的餐廳獲取其位置信息，然後計算是否滿足要求。如果一個地區有100家餐廳的話，我們就要進行100次位置計算操作了，如果應用到谷歌、百度地圖這種超大資料庫中，這種方法便必定不可行了。R樹就很好的解決了這種高維空間搜索問題。它把B樹的思想很好的擴展到了多維空間，採用了B樹分割空間的思想，併在添加、刪除操作時採用合併、分解結點的方法，保證樹的平衡性。因此，R樹就是一棵用來存儲高維數據的平衡樹。相對於B-Tree，R-Tree的優勢在於範圍查找。

6.8小結

使用索引可以幫助我們從海量的數據中快速定位想要查找的數據，不過索引也存在一些不足，比如占用存儲空間、降低資料庫寫操作的性能等，如果有多個索引還會增加索引選擇的時間。當我們使用索引時，需要平衡索引的利（提升查詢效率）和弊（維護索引所需的代價）。

在實際工作中，我們還需要基於需求和數據本身的分佈情況來確定是否使用索引，儘管索引不是萬能的，但數據量大的時候不使用索引是不可想象的，畢竟索引的本質，是幫助我們提升數據檢索的效率。

附錄：演算法的時間複雜度

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。