浅谈浅谈MySQL的的B树索引与索引优化树索引与索引优化
MySQL的MyISAM、InnoDB引擎默认均使用B+树索引（查询时都显示为“BTREE”），本文讨论两个问题：
为什么MySQL等主流数据库选择B+树的索引结构？
如何基于索引结构，理解常见的MySQL索引优化思路？
为什么索引无法全部装入内存
索引结构的选择基于这样一个性质：大数据量时，索引无法全部装入内存。
为什么索引无法全部装入内存？假设使用树结构组织索引，简单估算一下：
假设单个索引节点12B，1000w个数据行，unique索引，则叶子节点共占约100MB，整棵树最多200MB。
假设一行数据占用200B，则数据共占约2G。
假设索引存储在内存中。也就是说，每在物理盘上保存2G的数据，就要占用200MB的内存，索引:数据的占用比约为1/10。
1/10的占用比算不算大呢？物理盘比内存廉价的多，以一台内存16G硬盘1T的服务器为例，如果要存满1T的硬盘，至少需要
100G的内存，远大于16G。
考虑到一个表上可能有多个索引、联合索引、数据行占用更小等情况，实际的占用比通常大于1/10，某些时候能达到1/3。在
基于索引的存储架构中，索引:数据的占用比过高，因此，索引无法全部装入内存。
其他结构的问题
由于无法装入内存，则必然依赖磁盘（或SSD）存储。而内存的读写速度是磁盘的成千上万倍（与具体实现有关），因此，
核心问题是“如何减少磁盘读写次数”。
首先不考虑页表机制，假设每次读、写都直接穿透到磁盘，那么：
线性结构：读/写平均O(n)次
二叉搜索树（BST）：读/写平均O(log2(n))次；如果树不平衡，则最差读/写O(n)次
自平衡二叉搜索树（AVL）：在BST的基础上加入了自平衡算法，读/写最大O(log2(n))次
红黑树（RBT）：另一种自平衡的查找树，读/写最大O(log2(n))次
BST、AVL、RBT很好的将读写次数从O(n)优化到O(log2(n))；其中，AVL和RBT都比BST多了自平衡的功能，将读写次数降
到最大O(log2(n))。
假设使用自增主键，则主键本身是有序的，树结构的读写次数能够优化到树高，树高越低读写次数越少；自平衡保证了树结构
的稳定。如果想进一步优化，可以引入B树和B+树。
B树解决了什么问题
很多文章将B树误称为B-（减）树，这可能是对其英文名“B-Tree”的误解（更有甚者，将B树称为二叉树或二叉搜索树）。特
别是与B+树一起讲的时候。想当然的认为有B+（加）树就有B-（减）树，实际上B+树的英文名是“B+-Tree”。
如果抛开维护操作，那么B树就像一棵“m叉搜索树”（m是子树的最大个数），时间复杂度为O(logm(n))。然而，B树设计了一
种高效简单的维护操作，使B树的深度维持在约log(ceil(m/2))(n)~logm(n)之间，大大降低树高。
- 1
- 2
前往页