數(shù)據(jù)結(jié)構(gòu)

二叉排序樹（Binary Sort Tree）

規(guī)則

1. 若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值
2. 若右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值
3. 它的左、右子樹也分別為二叉排序樹（遞歸定義）

說明

????二叉查找樹查找比較方便，因為每次經(jīng)過一次節(jié)點時，最多減少一半的可能。極端情況下，會出現(xiàn)所有節(jié)點位于同一側(cè)的情況，直觀上看就是一條直線，這種情況的查詢效率比較低。因此需要對二叉樹左右子樹的高度作平衡化處理，這就是平衡二叉樹。

平衡二叉樹（Balance Binary Tree）

規(guī)則

1. 左右子樹的高度差的絕對值不超過1
2. 左右子樹都是平衡二叉樹（遞歸定義）

說明

????常見的實現(xiàn)方式為：紅黑樹，平衡二叉查找樹（AVL）,替罪羊樹，樹堆（Treap），伸展樹。在這樣的平衡樹中進行查找，總共比較節(jié)點的次數(shù)不超過樹的高度，查詢效率得到提高，時間復(fù)雜度為O(logn)。

平衡多路查找樹（B樹或B-樹）

規(guī)則

1. 每個節(jié)點至多可以擁有m棵子樹
2. 根節(jié)點，只有至少2個節(jié)點
3. 非根非葉的節(jié)點至少有Ceil(m/2)個子樹（Ceil表示向上取整），例如5階B樹，每個節(jié)點至少3個子樹
4. 所有葉子節(jié)點位于同一層，意思是從根到葉子節(jié)點的每一條路徑都有同樣的長度

說明

????B樹查詢與二叉排序樹類似，從根節(jié)點依次比較每個節(jié)點，因為每個節(jié)點中關(guān)鍵字和左右子樹都是有序的。

B+樹

規(guī)則

1. 有n棵子樹的節(jié)點含有n個關(guān)鍵字，每個關(guān)鍵字不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)保存在葉子節(jié)點
2. 所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接
3. 非葉子節(jié)點看成是索引部分，結(jié)點中僅含其子樹（根節(jié)點）中的最大（或最?。╆P(guān)鍵字

說明

????B+樹查找過程與B樹類似，只不過查找時，如果在非葉子節(jié)點上的關(guān)鍵字等于給定值，并不終止，而是繼續(xù)沿著指針直到葉子節(jié)點。因此對于B+樹，不管查找成功或失敗，每次查找都是走了一條從根到葉子節(jié)點的路徑。

????通常在B+Tree上有兩個頭指針，一個指向根節(jié)點，另一個指向關(guān)鍵字最小的葉子節(jié)點，而且所有葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈式環(huán)結(jié)構(gòu)（雙向循環(huán)鏈表）。因此可以對B+Tree進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節(jié)點開始，進行隨機查找。

實現(xiàn)

MyISAM索引實現(xiàn)

????MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉結(jié)點的data域存放的是數(shù)據(jù)記錄的地址。

主索引(主鍵)

輔助索引

????在 MyISAM 中,主索引和輔助索引(Secondary key)在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求 key 是唯一的,而輔助索引的 key 可以重復(fù)。

說明

????同樣也是一顆B+Tree，data域保存數(shù)據(jù)記錄的地址。因此，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄。

????MyISAM的索引方式也叫做“非聚集”的，之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分。

InnoDB索引實現(xiàn)

????雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)，但具體實現(xiàn)方式卻與MyISAM截然不同。

????第一個重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道，MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結(jié)構(gòu)，這棵樹的葉結(jié)點data域保存了完整的數(shù)據(jù)記錄。這個索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。

主索引(主鍵)

輔助索引

說明

????InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT（占用4個字節(jié)）或BIGINT（占用8個字節(jié)），指針類型也一般為4或8個字節(jié)，也就是說一個頁（B+Tree中的一個節(jié)點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值，為方便計算，這里的K取值為10^{3）。也就是說一個深度為3的B+Tree索引可以維護10}3 * 10^3 * 10^3 = 10億 條記錄。實際情況中每個節(jié)點可能不能填充滿，因此在數(shù)據(jù)庫中，B+Tree的高度一般都在2~4層。mysql的InnoDB存儲引擎在設(shè)計時是將根節(jié)點常駐內(nèi)存的，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。

????InnoDB 要求表必須有主鍵(MyISAM 可以沒有)，如果沒有顯式指定，則 MySQL系統(tǒng)會自動選擇一個可以唯一標識數(shù)據(jù)記錄的列作為主鍵,如果不存在這種列，則MySQL 自動為 InnoDB 表生成一個隱含字段作為主鍵,類型為長整形。

????同時,請盡量在 InnoDB 上采用自增字段做表的主鍵。因為 InnoDB 數(shù)據(jù)文件本身是一棵B+Tree，非單調(diào)的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持 B+Tree 的特性而頻繁的分裂調(diào)整，十分低效,而使用自增字段作為主鍵則是一個很好的選擇。如果表使用自增主鍵,那么每次插入新的記錄，記錄就會順序添加到當前索引節(jié)點的后續(xù)位置，當一頁寫滿,就會自動開辟一個新的頁。

聚簇索引

????InnoDB 使用的是聚簇索引，將主鍵組織到一棵B+樹中， 而行數(shù)據(jù)就儲存在葉子節(jié)點上， 若使用"where id = 14"這樣的條件查找主鍵，則按照 B+樹的檢索算法即可查找到對應(yīng)的葉節(jié)點，之后獲得行數(shù)據(jù)。 若對 Name 列進行條件搜索，則需要兩個步驟:

• 第一步、在輔助索引 B+樹中檢索 Name，到達其葉子節(jié)點獲取對應(yīng)的主鍵。
• 第二步、使用主鍵在主索引B+樹種再執(zhí)行一次 B+樹檢索操作，最終到達葉子節(jié)點即可獲取整行數(shù)據(jù)。

非聚簇索引

????MyISM 使用的是非聚簇索引, 非聚簇索引的兩棵 B+樹看上去沒什么不同, 節(jié)點的結(jié)構(gòu)完全一致只是存儲的內(nèi)容不同而已, 主鍵索引 B+樹的節(jié)點存儲了主鍵, 輔助鍵索引B+樹存儲了輔助鍵。 表數(shù)據(jù)存儲在獨立的地方, 這兩顆 B+樹的葉子節(jié)點都使用一個地址指向真正的表數(shù)據(jù), 對于表數(shù)據(jù)來說, 這兩個鍵沒有任何差別。 由于索引樹是獨立的, 通過輔助鍵檢索無需訪問主鍵的索引樹。