數(shù)據(jù)結(jié)構(gòu)
二叉排序樹（Binary Sort Tree）
規(guī)則
- 若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值
- 若右子樹不空再菊，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值
- 它的左、右子樹也分別為二叉排序樹（遞歸定義）
說明
????二叉查找樹查找比較方便，因為每次經(jīng)過一次節(jié)點時语卤，最多減少一半的可能追逮。極端情況下酪刀，會出現(xiàn)所有節(jié)點位于同一側(cè)的情況，直觀上看就是一條直線钮孵，這種情況的查詢效率比較低骂倘。因此需要對二叉樹左右子樹的高度作平衡化處理，這就是平衡二叉樹巴席。
平衡二叉樹（Balance Binary Tree）
規(guī)則
- 左右子樹的高度差的絕對值不超過1
- 左右子樹都是平衡二叉樹（遞歸定義）
說明
????常見的實現(xiàn)方式為：紅黑樹历涝，平衡二叉查找樹（AVL）,替罪羊樹，樹堆（Treap）漾唉，伸展樹荧库。在這樣的平衡樹中進行查找，總共比較節(jié)點的次數(shù)不超過樹的高度赵刑，查詢效率得到提高分衫，時間復(fù)雜度為O(logn)。
平衡多路查找樹（B樹或B-樹）
規(guī)則
- 每個節(jié)點至多可以擁有m棵子樹
- 根節(jié)點般此，只有至少2個節(jié)點
- 非根非葉的節(jié)點至少有Ceil(m/2)個子樹（Ceil表示向上取整）蚪战，例如5階B樹牵现，每個節(jié)點至少3個子樹
- 所有葉子節(jié)點位于同一層，意思是從根到葉子節(jié)點的每一條路徑都有同樣的長度
說明
????B樹查詢與二叉排序樹類似邀桑，從根節(jié)點依次比較每個節(jié)點瞎疼，因為每個節(jié)點中關(guān)鍵字和左右子樹都是有序的。
B+樹
規(guī)則
- 有n棵子樹的節(jié)點含有n個關(guān)鍵字壁畸，每個關(guān)鍵字不保存數(shù)據(jù)贼急，只用來索引，所有數(shù)據(jù)保存在葉子節(jié)點
- 所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息捏萍，及指向含這些關(guān)鍵字記錄的指針竿裂，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接
- 非葉子節(jié)點看成是索引部分，結(jié)點中僅含其子樹（根節(jié)點）中的最大（或最姓彰帧）關(guān)鍵字
說明
????B+樹查找過程與B樹類似腻异，只不過查找時，如果在非葉子節(jié)點上的關(guān)鍵字等于給定值这揣，并不終止悔常，而是繼續(xù)沿著指針直到葉子節(jié)點。因此對于B+樹给赞，不管查找成功或失敗机打，每次查找都是走了一條從根到葉子節(jié)點的路徑。
????通常在B+Tree上有兩個頭指針片迅，一個指向根節(jié)點残邀，另一個指向關(guān)鍵字最小的葉子節(jié)點，而且所有葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈?zhǔn)江h(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取值為103）槽驶。也就是說一個深度為3的B+Tree索引可以維護103 * 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)會自動選擇一個可以唯一標(biāo)識數(shù)據(jù)記錄的列作為主鍵,如果不存在這種列烤镐，則MySQL 自動為 InnoDB 表生成一個隱含字段作為主鍵,類型為長整形蛋济。
????同時,請盡量在 InnoDB 上采用自增字段做表的主鍵棍鳖。因為 InnoDB 數(shù)據(jù)文件本身是一棵B+Tree炮叶，非單調(diào)的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持 B+Tree 的特性而頻繁的分裂調(diào)整，十分低效,而使用自增字段作為主鍵則是一個很好的選擇渡处。如果表使用自增主鍵,那么每次插入新的記錄镜悉，記錄就會順序添加到當(dāng)前索引節(jié)點的后續(xù)位置，當(dāng)一頁寫滿,就會自動開辟一個新的頁医瘫。
聚簇索引
????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ù)來說, 這兩個鍵沒有任何差別。 由于索引樹是獨立的, 通過輔助鍵檢索無需訪問主鍵的索引樹允趟。
