MySQL BTREE索引

个人本事有限，如有错误请指出，共同砚习。
目次：

一、二叉树、B树、B+树及其特点

二、聚簇索引和二级索引

三、索引存储数据量估算

四、索引插入过程

五、索引页面接纳

六、参考文档

一、二叉树、B树、B+树及其特点

二叉树

特点：

• 全部非叶子结点至多拥有两个儿子（Left和Right）；
  
• 每个结点各存储一个关键字；
  
• 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
  

B树

特点：

• B树中每个节点可以有多个关键字，而且每个节点可以有多个孩子；
  
• B树中同一键值不会出现多次，要么在叶子节点上，要么在内结点上；
  
• 由于B树的每个结点都存真实的数据，会导致每一个结点存储的数据量变小，整个B树的层数就会相对变高，数据量变大之后，终极会酿成一个瘦高个子，导致搜索或修改的性能就会越低。
  
• 查找效率与键在B树中的位置有关，在叶子结点的时间，最大时间复杂度为O(log n)，在根结点的时间，最小时间复杂度为O(1)；
  
• B树中全部节点的孩子节点数中的最大值称为B树的阶，记为M
  
• 树中的每个节点至多有M棵子树
  
• 若根节点不是终端节点,则至少有两棵子树
  
• 除根节点外全部非叶节点至少有m/2棵子树
  
• 全部的叶节点须要出如今同一条理上
  
• 树中全部节点的均衡因子都即是0
  

B+树

特点：

• B+树的键肯定会出如今叶子结点上，同时也大概在非叶子结点中重复出现。简单说，B+树的内结点存储的都是键值，键值对应的具体数据都存储在叶子结点上；
  
• B+树的内结点只存键值，故存储的纪录比B树内结点多很多，故B+树是横向扩展的，终极会长成一个矮胖子，在搜索时，终极只须要从根到叶子结点遍历层数(比B树这个高瘦子的层数少很多)个结点即可，性能会比力高。
  
• B+树的时间复杂度是固定的O(log n)；
  

MySQL BTREE索引利用的就是B+树存储，下面是一个BTREE索引大抵布局：

• 页号随机分布，逻辑上连续，但物理上并不是连续的。
  
• 在每一层的最左边节点页面的最左边位置，都有一个Min纪录。
  
• 全部叶子节点，从左到右，从小到大，都是以双向链表链在一起的。
  
• 叶子结点中的data：
  1.假如聚簇索引，则data存储除主键列之外的其他全部列组合；
  2.假如二级索引，则data存储的就是这行纪录对应的主键列组合，索引遍历时可根据此主键枚举行回表查找。
  

二、聚簇索引和二级索引

聚簇索引

• 一个表中可以有多个索引，但每一个表都有一个索引是存储了全部数据的，这个索引一样平常被称为“聚簇索引”。
  
• 聚簇索引在一个表中只有一个，且是创建在主键上的，主键列可以是被潜伏的rowid列，也可以是自增列，还可以是界说的非空组合列等。
  
• 聚簇索引占用的空间是比力大的，因为索引包含行的全部列数据。
  布局分类如下：
  自界说主键的聚簇索引
  索引布局：【主键列】【TRXID】【ROLLPTR】【其他建表创建的非主键列】
  加入纪录比力的列：主键列
  内结点Key列：【主键列】+PageNo指针
  未界说主键的聚簇索引
  索引布局：【ROWID】【TRXID】【ROLLPTR】【其他建表创建的非主键列】
  加入纪录比力的列：只ROWID一列而已
  内结点Key列：【ROWID】+PageNo指针
  

二级索引

• 聚簇索引之外的全部索引都称为二级索引。
  布局分类如下：
  自界说主键的二级唯一索引
  索引布局：【唯一索引列】【主键列】
  加入纪录比力的列：【唯一索引列】【主键列】
  内结点Key列：【唯一索引列】+PageNo指针
  自界说主键的二级非唯一索引
  索引布局：【非唯一索引列】【主键列】
  加入纪录比力的列：【非唯一索引列】【主键列】
  内结点Key列：【非唯一索引列】【主键列】+PageNo指针
  未界说主键的二级唯一索引
  索引布局：【唯一索引列】【ROWID】
  加入纪录比力的列：【唯一索引列】【ROWID】
  内结点Key列：【唯一索引列】+PageNo指针
  未界说主键的二级非唯一索引
  索引布局：【非唯一索引列】【ROWID】
  加入纪录比力的列：【非唯一索引列】【ROWID】
  内结点Key列：【非唯一索引列】【ROWID】+PageNo指针
  

三、索引存储数据量估算

key数据存储量估算：
若每个页可以存1000个key，而且树的高度是4，那么

• 第一层页面，只有一个页，存储key 1000个；
  
• 第二层可以存储1001个页，相应的key就是 1000*1001；
  
• 第三层可以存储的1000*1001+1个页，相应的key就是1000*（1000*1001+1），约100亿条；
  
• 第四层为叶子结点，可以存储1000*（1000*1001+1）+1个页，每个页存储的数据量就会比内结点的1000少，因为有data部分，假设存256个，那么这个B+树存满的情况下，共可以存储（1000*（1000*1001+1）+1）*256条纪录，2562,5625,6256，约2500亿条，估计mysql是没机遇处理这么大数据量的单表了。
  纵然是千亿级别的数据量，要查找一个纪录的话，也只须要4个页面的IO即可完成终极数据的定位，在叶子结点中，只须要做一次内存级的二分查找即可找到具体的数据纪录。
  

四、索引插入过程

条件条件如下：

• 假设每个页面最多可以插入三条纪录，插入第四条的时间就会发生分裂；
  
• 插入数据为键值时，但我们只关注键，值可以不消关注，就简单地以data取代即可；
  
• 插入的数据序列为：10，20，5，8，23，22，50，21，53，40，9；
  
• 为了简单明白一些，key就是一个简单的INT范例的数字；
  
• 假设根结点页面号为100。
  

插入步调
步调一
因为索引中还没有数据，以是此时的B+树只有一个空的根结点，又由于一个页只能存3个key，起首将10，20，5插入进去（实际上此步发生了3次插入），然后在页面内做数据排序，最闭幕果如下图：


步调二：
由于根页面已经写满，此时插入8，将发生分裂（根页面分裂），大抵步调如下：
注意：在分裂过程中，根结点始终是不会变的，不管酿成多大的树，根结点的页面号始终如一。

• 起首，创建一个新的叶子结点，假设申请的页面号是101。B+树的内结点和叶子结点实际上是通过差别的段来构造的，这里由于根结点同时还是叶子结点，内里存储的数据都是全部的数据，而不但是key，以是这里从叶子结点取，来创建一个新的叶子结点。
  
• 然后将原页面的全部纪录复制到新页面中，原根页面的最小虚纪录要指向新叶子结点，同时将原根页面中的纪录全部删除；
  
• 末了将根页面的Min纪录指针指向新的叶子结点101号页面，如许就构成一个B+树形布局了。如下图：上面的分裂动作已完成，开始插入数据8，此时直接定位到叶子结点101号页面，在这个页面插入时发现还是没有空间，以是又涉及一次叶子结点的分裂，步调如下：
  
• 起首，创建一个新的叶子结点，假设页面号是102；
  
• 将101号页面的一部分数据移到102号页面中，这里的一部分一样平常是指一半，这里可以假设每次移已往1条；
  
• 101和102号页面都是叶子结点，称为兄弟关系，他们须要构成双向链表；
  
• 将一半数据移到102号页面之后，此时这个页面须要须要与根结点挂上关系，要做的就是将20这条纪录的key取出来，然后加上一个指针，构成一条新的纪录插入到根页面中，如下两图：
  至此，全部的分裂预备工作都已完毕，终于可以插入数据8了。步调很简单，从根结点开始搜索，8比20小，就从Min这个纪录上找到对应的叶子节点，101号页面，然后实行插入，因为是排序的，以是插入到5和10之间（这是为了可以简单直白地看到，着实内部的排序构造不是如许的），如许，101号页面就有5、8、10三条纪录了。如下图所示：
  
  步调三：
  插入数据23、22，因为这个数据都是大于20的，以是找到相应的叶子节点102号页面实行插入，而且空间富足，以是直接插入这两条纪录，插入后B+树布局如下图所示：
  
  步调四：
  继续插入数据50，因为大于20，找到102号页面，发现页面已满，实行叶子结点的分裂，分裂同上面叶子结点的分裂步调。分裂后如图所示：
  然后插入50
  接着插入21
  接着插入53
  此时叶子结点均已写满，下次数据插入必将产生分裂。
  

步调五：
插入数据40，发现比根结点23大，找到103号页面，发现已满，实行分裂，分裂同上面叶子结点的分裂步调。分裂后如图所示：

插入40：
步调六：
继续插入下一个数据9，因为比20小，找到101号页面，发现已满，须要做叶子结点分裂，如下图：

叶子节点分裂之后，须要与根结点产生父子关系，但是不幸，根结点也已满，须要做根页面的分裂。新建一个结点106，将根结点100号页面的数据复制已往，而根结点100始终是根结点，如下图所示。
此时106号页面还是满的，key 10 还是无法写到内结点106上，须要做一次内结点分裂，新建内结点107号页面，分裂后如下图：
分裂后105号页面就可以找到本身的爸爸了，如下图：
此时，只是完成了分裂，数据9还没有完成插入操纵，此时很显着，插入时找到页面101实行插入即可，完成后如下图所示：
至此，全部的数据插入操纵已经完成。
五、索引页面接纳

传统B+树的数据删除，一样平常都会有一个所谓的填充因子，来控制页面数据的删除比例，假如数据量小于这个填充因子所表现的数据量，就会有节点归并，这与分裂是相对应的。
InnoDB的实现与传统B+树算法有差别之处，InnoDB在删除索引数据时，会先查抄当前页剩余的纪录数，假如只剩下一条纪录，就会直接将这个页面从B+树中摘除，也只有这种情况，InnoDB才会接纳一个页面，InnoDB的页面没有归并一说，但是对于根节点，纵然索引数据全部删除，根节点页依然存在，只不外是以空页的形式存在。
下面举个例子形貌索引删除过程，条件条件与前面插入纪录时一致。


假设初始B+树如下（为上面插入完成后的B+树）：删除数据 50

删除数据 20
删除数据 10
删除数据 23
删除数据 40
删除数据 53
删除数据 8，9，21
删除数据 5
删除数据 22
删除过程全部竣事，终极得到一个空的索引页。
六、参考文档

《MySQL运维内参》
B+树动画演示：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html