前提： 以下的一些數(shù)據(jù)結(jié)構(gòu)大家需提前知道，否則看起來(lái)會(huì)比較有困難，大家也可以按照本文所提到的知識(shí)點(diǎn)去主動(dòng)查閱學(xué)習(xí)。

1. Hash表？No

因考慮到在數(shù)據(jù)檢索的過(guò)程中經(jīng)常會(huì)有范圍的查詢(xún)（如下），而hash表不能提供這種功能。

SELECT * FROM hero WHERE age>5 AND age<20;

使用哈希算法實(shí)現(xiàn)的索引雖然可以做到快速檢索數(shù)據(jù)，但是沒(méi)辦法做數(shù)據(jù)高效范圍查找，因此哈希索引是不適合作為 Mysql 的底層索引的數(shù)據(jù)結(jié)構(gòu)。

2. 二叉查找樹(shù)(BST)？No

二叉查找樹(shù)（Binary Search Tree）雖然可以達(dá)到范圍搜索，但是在樹(shù)的插入過(guò)程中，如果插入的數(shù)據(jù)本來(lái)就是有順序的，那么就會(huì)形成一條鏈（如下），它的最壞情況是O(n)。 

3. 紅黑樹(shù)？No

紅黑樹(shù)雖然看似達(dá)到了平衡狀態(tài)，但是也會(huì)有極端情況存在，和上述BST樹(shù)一樣，雖然不會(huì)成為鏈狀，但是紅黑樹(shù)會(huì)存在右傾的現(xiàn)象。 

在數(shù)據(jù)庫(kù)中的基本主鍵自增操作，主鍵一般都是數(shù)百萬(wàn)數(shù)千萬(wàn)的，如果紅黑樹(shù)存在這種問(wèn)題，對(duì)于查找性能而言也是巨大的消耗，我們數(shù)據(jù)庫(kù)不可能忍受這種無(wú)意義的等待的。

4. 平衡二叉樹(shù)(AVL)？差那么二點(diǎn)意思

平衡二叉樹(shù)，英文翻譯為Balanced Binary Tree，為啥叫AVL呢？ AVL 是大學(xué)教授G.M. Adelson-Velsky 和 E.M. Landis 名稱(chēng)的縮寫(xiě)，他們提出的平衡二叉樹(shù)的概念，為了紀(jì)念他們，將平衡二叉樹(shù)稱(chēng)為 AVL樹(shù)。

AVL樹(shù)本質(zhì)上是一顆二叉查找樹(shù)，但是它又具有以下特點(diǎn)：

• 它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，
• 左右兩個(gè)子樹(shù)也都是一棵平衡二叉樹(shù)。

它不存在紅黑樹(shù)這種右傾的現(xiàn)象，也具備數(shù)據(jù)高效范圍查找的能力，但是數(shù)據(jù)庫(kù)查詢(xún)數(shù)據(jù)的瓶頸在于磁盤(pán)的IO，樹(shù)節(jié)點(diǎn)在磁盤(pán)空間中存儲(chǔ)可能是不連續(xù)的，假設(shè)我們一次IO讀取一個(gè)樹(shù)的節(jié)點(diǎn)，此次讀入內(nèi)存的這頁(yè)中沒(méi)有其他樹(shù)的節(jié)點(diǎn)，那么每讀取一個(gè)樹(shù)的節(jié)點(diǎn)，就要進(jìn)行一次IO，這是多么消耗時(shí)間啊，所以我們?cè)O(shè)計(jì)數(shù)據(jù)庫(kù)索引時(shí)需要首先考慮怎么盡可能減少磁盤(pán) IO 的次數(shù)。 磁盤(pán)讀取依靠的是機(jī)械運(yùn)動(dòng)，分為尋道時(shí)間、旋轉(zhuǎn)延遲、傳輸時(shí)間三個(gè)部分，這三個(gè)部分耗時(shí)相加就是一次磁盤(pán)IO的時(shí)間；這個(gè)花費(fèi)的時(shí)間成本是內(nèi)存訪問(wèn)的十幾萬(wàn)倍左右。 正是由于磁盤(pán)IO是非常昂貴的操作，所以計(jì)算機(jī)操作系統(tǒng)對(duì)此做了優(yōu)化：預(yù)讀；每一次IO時(shí)，不僅僅把當(dāng)前磁盤(pán)地址的數(shù)據(jù)加載到內(nèi)存，同時(shí)也把相鄰數(shù)據(jù)也加載到內(nèi)存緩沖區(qū)中。因?yàn)榫植款A(yù)讀原理說(shuō)明：當(dāng)訪問(wèn)一個(gè)地址數(shù)據(jù)的時(shí)候，與其相鄰的數(shù)據(jù)很快也會(huì)被訪問(wèn)到。每次磁盤(pán)IO讀取的數(shù)據(jù)我們稱(chēng)之為一頁(yè)（page）。一頁(yè)的大小與操作系統(tǒng)有關(guān)，一般為4k或者8k。這也就意味著讀取一頁(yè)內(nèi)數(shù)據(jù)的時(shí)候，實(shí)際上發(fā)生了一次磁盤(pán)IO。

相關(guān)術(shù)語(yǔ)解釋?zhuān)?/strong>