B+树与数据库索引

目录

• B+树定义

• B+树查询操作实现

• B+树插入操作实现

• B+树删除操作实现

• 数据库索引原理

• MySQL索引简介

  • MyISAM索引

  • InnoDB 索引

• 数据库查询机制

• MySQL索引常见问题

• MySQL存储引擎索引类型使用B+树而不是B树？

• InnoDB存储引擎中，一棵 B+ 树可以存放多少行数据？

• 为什么InnoDB主键索引推荐自增字段？

• InnoDB自增字段用完之后，会不会报错？

• 附：B+树实现源代码

为了应对大规模数据检索需要，一种支持多路平衡搜索的B-树出现了，不仅解决了二叉树容易退化为单链表的问题，还能够以更少的磁盘I/O提高查询效率，然而B-树索引节点中记录数据导致性能没有得到最大发挥，于是出现了B+树。

B+树定义

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下：

（1）每个节点最多有m个子节点

（2）除根节点外，每个节点至少有m/2个子节点，注意如果结果除不尽，就向上取整，比如5/2=3。

（3）根节点要么是空，要么是独根，否则至少有2个子节点

（4）有k个子节点的节点必有k个关键码

（5）叶节点的高度一致

一个B+树示例图如下： B+树的查找与B树不同表现为：

• 当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。

• 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字从小到大顺序链接；

• 各层节点中的关键码均是下一层相应节点中的最大或者最小的关键码的复写。

本文使用最小关键码表示，用类实现的B+树节点定义如下： 其中DataEntry代表节点里的数据记录或者键值记录，存储结构为单链表。对于非叶子节点，每个DataEntry代表键值记录（此时value为空），指向子节点位置。

B+树查询操作实现

因为B+树有两个指针：一个指示树索引的树根指针root，另一个是指示叶子数据节点的数据指针sqt。因此给定记录查找过程为：如果树根指针不为空，那么沿着树索引逐层搜索记录所在的分支，直到到达叶子节点；如果树根节点为空但数据指针不为空，那么此时只有一个叶子节点，从sqt指针所指示的链表遍历。记录搜索的程序示例如下：

B+树插入操作实现

为了保证插入节点不破坏树的性质，记录先插入到叶子节点的合适位置，然后再检查是否违规，插入违规表现为节点记录数量超过树的阶数m。如果违规则需要进行分裂操作。而如何找到合适的叶子节点，则需要利用树的键值索引。特别地，根据树的定义可知，根节点至少有2个节点，当初始建立节点插入一个记录，此时树根为空，只需创建一个叶子数据节点和包含的数据项，然后用sqt指针指向该节点即可：

DataEntry<K, V> leafEntry = new DataEntry(entry.key, entry.value);
BPlusTreeNode leafNode = new BPlusTreeNode(NodeType.LEAF, leafEntry);
this.sqt = leafNode;

当叶子节点数目超过阶数m时候，分裂为两个节点，同时构建有两个键值的树根节点，依次类推。下面列举插入过程中几种情况并提供操作程序示例：

0. 正常插入数据，无需调整，例如插入记录9 此时从根节点出发沿着键值搜索到达第一个叶子节点，将新的数据记录entry插入到第一个元素之前，插入逻辑用程序表示为：

private void addEntry(BPlusTreeNode<K, V> node, DataEntry<K, V> entry) {
    DataEntry<K, V> current = node.nextEntry;
    DataEntry<K, V> previous = null;
    //遍历键值链表插入到合适位置
    while (current != null && entry.key.compareTo(current.key) > 0) {
        previous = current;
        current = current.nextEntry;
    }
    entry.nextEntry = current;
    if (previous != null)
        previous.nextEntry = entry;
    else
        node.nextEntry = entry;
}

1. 插入节点需要递归向上分裂，例如插入记录20

插入20导致节点数据记录数量超过阶数3，此时插入节点从数据记录中间位置（记录21）拆分，将中间记录当做键值提升到父节点，此时父节点键值数目又超过最大数目限制，需要对父节点键值进一步拆分。 这个步骤是一个递归过程，直到根节点。 如果根节点键值数目也超限，则重建新的根节点。 这里在上一步添加记录之后进行一个调整操作，详细步骤如下：

a. 寻找待分裂节点的中间数据记录位置

//将中间位置的数据提升为键值，此时需要定位到链表的中间位置
int midKeySize = insertedNode.size / 2;
//midKeyIndex为偶数，节点元素数量为 midKeySize，否则元素数量为 midKeySize+1
midKeySize = ((midKeySize & 1) == 0) ? midKeySize : (midKeySize + 1);
int index = 1;
DataEntry entry = insertedNode.nextEntry;
while (index < midKeySize) {
    entry = entry.nextEntry;
    index++;
}

b. 创建新的节点，并插入当前节点之后

//在当前插入节点之后插入拆分的节点
NodeType nodeType = insertedNode.nodeType;
BPlusTreeNode splitNode = new BPlusTreeNode(nodeType, null);
splitNode.nextSibling = insertedNode.nextSibling;
if (insertedNode.nextSibling != null)
    insertedNode.nextSibling.prevSibling = splitNode;
splitNode.prevSibling = insertedNode;
insertedNode.nextSibling = splitNode;
//将原来data后半部分数据挂到拆分的新节点上
splitNode.nextEntry = entry.nextEntry;
entry.nextEntry = null;
splitNode.size = insertedNode.size - midKeySize;
insertedNode.size = midKeySize;
splitNode.parentNode = insertedNode.parentNode;

c. 父节点中插入新的键值

DataEntry newEntry = new DataEntry(entry.key, null);
DataEntry parentEntry = insertedNode.parentNode.nextEntry;
DataEntry currentEntry = parentEntry;
DataEntry previousEntry = null;
/**
 键值提到父节点，通过插入排序插入到合适位置
 */
while (currentEntry != null && currentEntry.key.compareTo(entry.key) > 0) {
    previousEntry = currentEntry;
    currentEntry = currentEntry.nextEntry;
}
newEntry.nextEntry = currentEntry;
if (previousEntry != null)
    previousEntry.nextEntry = newEntry;
else
    insertedNode.parentNode.nextEntry = newEntry;
newEntry.childNode = insertedNode;
newEntry.nextEntry.childNode = splitNode;

2. 插入超过当前树最大值的记录并且需要递归向上分裂，如插入记录100 这种情况跟上一种情况类似，执行同样的调整过程，区别在于在执行调整前需要先更新最大键值： 更新最大键值也是一个递归过程：将父节点的键值链表最后一个记录修改为当前最大值。skipLast2Entry方法跳到最后两个记录所在位置，因为该方法经常用于在队尾删除记录，故抽出作为公用方法。于是归纳插入节点的处理流程：

• 如果当前B+树节点为空，则创建新的根节点和叶子节点，叶子节点存储当前值。并令叶子节点的父指针指向根节点，根节点中的数据记录子节点指针指向当前叶子节点；

• 如果插入节点类型为叶子节点，直接进入节点内部，遍历键值链表插入新记录。插入之后再判断节点是否违规，如果违规则需要分裂调整；

• 如果当前树节点不为空，通过比较当前节点的键值和根节点的键值链表中的每个键值，定位所属分支，递归以上步骤。

于是总体处理流程用代码描述为：

B+树删除操作实现

B+树删除操作流程跟插入流程类似，也是先通过树索引定位到所在分支叶子节点，然后通过遍历叶子节点删除目标记录。不同之处在于，删除节点记录之后，节点记录总数可能会少于阶数m的一半，此时会涉及到节点的租借和合并操作。特别地，当整棵树只剩下两个叶子节点而发生合并的时候，分支数量也变为1，为了保证树的性质不被破坏，树根指针要变成空，只保留指向叶子节点的数据指针sqt，后续对记录的删除，通过sqt直接操作在这唯一的节点上。下面列举删除操作的几种情况和程序实现：

0. 删除节点不影响B+树的性质，例如删除91 这种情况比较简单，定位到数据所在叶子节点直接删除记录即可。

1.删除最大元素需要更新父节点键值，例如删除97

这种情况跟上一种情况类似，但需要更新当前最大键值，程序实现为：

代码覆盖到前面两种情况，最后一行是删除记录之后需要调整，针对的是以下几种情况

2. 删除节点后需要从兄弟节点租借才能满足B+树性质，例如 删除51

因为删除记录导致节点小于最小数据条数，需要从兄弟节点租借记录： 将左兄弟节点数据记录最后一个记录移到当前节点数据记录队列头部，同时更新兄弟节点的键值最大值：

其中方法removeLastEntry功能是删除兄弟节点的最大节点，然后用前一个记录的值作为键值：

再次看到方法skipLast2Entry的调用，这里取出倒数第二个记录就很方便。示例中从左兄弟节点租借记录，从右兄弟节点租借逻辑类似。

3. 删除节点后需要跟兄弟节点合并才能满足B+树定义，例如删除59 删除的记录是当前节点的最大值导致键值发生变化，然后合并节点导致分支少了一个，需要从父节点删除一个键值。我们看到，在删除记录的同时更新最大键值可使得处理逻辑简单，在这之后进行节点的合并：将当前删除节点的数据挂在左兄弟节点的数据链表之后，然后更新左兄弟节点的最大键值并删除原来键值。程序代码如下： 这里同样以合并到左兄弟节点为例，合并到右兄弟节点逻辑类似。

4. 删除节点后的合并导致父节点不满足B+树性质，需要对父节点进行合并或者租借，例如删除63 这种情况就是上一种情况的更进一步，用到递归过程。因为删除父节点键值导致父节点的键值数量违规，所以此时需要以父节点为当前节点，继续按照前面的逻辑调整（通过调用方法removeEntry）。于是归纳出删除操作的处理流程：

• 先通过删除记录key查找到所在节点；

• 进入节点内部，删除在键值链表中的记录，然后进入删除之后的调整流程；

• 在删除调整过程

a. 判断左兄弟节点是否可以借最右边的记录，如果可以借，则将借过来的记录插入到当前节点的链表首部；否则左兄弟节点跟当前节点合并，然后递归处理以上过程直到根节点；

b. 判断右兄弟节点是否可以借最左边的记录，如果可以借，则将借过来的记录插入到当前节点的链表尾部；否则右兄弟节点跟当前节点合并，然后递归处理以上过程直到根节点。

总体代码处理逻辑如下：

数据库索引原理

数据库的数据，包括索引等数据，都是以数据文件的形式存储在磁盘上，数据库进行读写操作的时候需要读取磁盘数据到内存，不同于内存的随机读写耗时基本可以忽略不计，因为物理构造原因，磁盘读写数据涉及到磁头的机械移动寻址，更适合顺序的读取。因此对于磁盘读取的数据库，衡量其效率最重要的指标就是I/O读写次数。为了提升磁盘读取效率，往往根据数据局部性原理，每次I/O都是预取而不会只读想要的少部分数据，预取的数据以磁盘页为单位，这样做的好处是下次使用的数据刚好也在预读取的页中，就不需要再次加载磁盘页。因此B-树的设计就利用这种预读的性质，将节点大小设置为页大小，每次数据存取的时候，就申请一个磁盘页，这样就保证一个节点的数据物理上也在一个页里，加之计算机存储分配按照页对齐，就实现一个节点加载就需要一次I/O。然后比较其他的索引结构，比如红黑树，因为高度要大很多，逻辑上很近的节点，物理上可能很远，无法利用这种局部性原理，所以其I/O复杂度要高很多。而数据库如何基于页进行数据检索，接下来需要介绍下数据库的存储结构和页结构的相关知识。

数据库逻辑存储结构按照层次从高层到底层划分为表空间（table space）、段（segment）、扩充或者区（extent）、数据库块。逻辑结构如下图所示： 表空间是数据库的逻辑划分，一个表空间只能属于一个数据库。所有的数据库对象都存放在指定的表空间中，但主要存放的是表， 所以称作表空间。表空间从管理上划分为系统表空间、用户表空间、撤销表空间、临时表空间等。表空间的概念是Oracle首创的，MySQL没有真正意义上的表空间管理,MySQL的Innodb包含两种表空间文件模式，默认的共享表空间和每个表分离的独立表空间。在一个表空间中，为一个表、索引分配的所有磁盘空间就组成一个段。在正常情况下，一个表、索引就对应一个段。如果表、索引被分区，数据被分成几部分存放在几个表空间中，那么每一个表空间中的磁盘空间就组成表、索引的一个段。在这种情况下，一个表、索引就由多个段组成。扩充是一块连续的磁盘空间，是数据库中存储空间的分配单元，数据库系统按照此单位给需要磁盘空间的表、索引分配空间。数据库页又称为数据库块、逻辑页、逻辑块，内部存储数据记录，是数据库读写磁盘的单位，其页尺寸（也称为块尺寸）为操作系统页尺寸的倍数。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_ page_ size查看。

数据库的物理结构最终要通过数据文件来承接，数据文件(有时也称为主文件)通常有三种组织形式：堆组织表(heap-organized tables, heap files)、索引组织表(index-organized tables) 或 散列组织表(hash-organized tables, hashed files)：堆组织表(heap-organized tables)，记录不需要遵循任何特定的顺序，大多数情况下它们在文件中按写入顺序排列，当添加新记录时不需要进行任何文件内容的调整。但它需要额外的索引结构指向存储的数据记录的位置，以便进行搜索。索引组织表(Index-Organized Table) 将索引和数据记录存储在一起。以主键进行排序，二叉树的形式对表的数据进行存储。因为索引组织表已经按照主键对数据进行了排序，查找某个范围记录的效率非常高。散列组织表（hash-organized tables）中存储单位是桶（bucket），每个桶中包含若干条记录。主键的散列值决定了一条记录应该存储的桶。每个桶中的记录可以按添加顺序，也可以按主键排序存储。

为了加快数据的检索还有一种索引文件，通常数据文件和索引文件独立存储。主文件(数据文件)上的索引称为主索引。在大多数情况下，主索引构建在主键上，主键可以是一个键也可以是一组能标识记录的键。所有其他索引都称为辅助索引（Secondary indexes），辅助索引可以直接映射到数据记录位置，或者只是简单的映射到记录所对应的主键。多个辅助索引可以指向相同的记录，从而允许通过不同的字段和不同的索引来查找单个数据记录。主索引文件为每个搜索键保存唯一一个条目，而辅助索引可能为每个搜索键保存多个条目。如果数据记录的顺序和搜索键的顺序一致，则此索引称为聚簇索引。这种情况下索引和的数据记录通常存储在相同的文件中。如果数据存储在单独的文件中，并且其顺序和键的顺序不一致，则该索引称非聚簇索引。

MySQL索引简介

MySQL数据库存储引擎支持3种索引类型，分别是B+树索引，全文索引和哈希索引，而B+树索引是目前使用最广泛、最有效的索引。因为B+树的高扇出性，B+树的高度一般在2-4层，也就是说在查找数据的时候最多经过2-4次I/O。B+树索引可以分为聚集索引和辅助索引，但不管是聚集还是辅助的索引，其内部都为B+树结构，即高度平衡，叶子节点存放着所有的数据，两者不同的是叶子节点存放的是否是一整行的信息。在MySQL中，根据数据文件类型不同存在两种不同的存储引擎：MyISAM和InnoDB，下面分别描述这两种引擎上的索引：

MyISAM索引

MyISAM引擎使用堆组织表：数据和索引独立存储，在索引的叶子节点数据域中存放指向数据记录的地址，如下图在Col1主键列上建立主索引： 由图可知，索引记录随机插入而数据记录按顺序写入，两者顺序不一致，因此MyISAM索引也被称为非聚集索引。再按照非主键列Col2建立辅助索引，如下图所示： 可见，辅助索引（Secondary key）的叶子节点也是通过数据域指向数据记录地址，跟主索引的区别是辅助索引可以创建多个。

InnoDB 索引

InnoDB 引擎数据文件是索引存储结构，数据表的记录按照主键顺序存放，叶节点数据域保存了完整的数据记录，这种索引也叫做聚集索引，同样以Col1为主键建立主键索引，如下图所示： 然后再看下按照非主键列Col3建立辅助索引的示意图： 可见，InnoDB的辅助索引的叶子节点指向了主键ID，而不是完整的记录，此时如果查找完整的记录，需要根据主键ID二次查询。

数据库查询机制

如果数据库使用B+树索引，那么每个节点都是一个页，每次新建节点的时候，就会申请一个页空间。同一层上的节点之间，通过页的结构构成一个双向的链表（页文件头中的两个指针字段）。非叶子节点，包括了多个索引行，每个索引行里存储索引键和指向下一层页面的页面指针。最后是叶子节点，它存储了关键字和行记录，在节点内部（也就是页结构的内部）记录之间是一个单向的链表，链表记录数量可以达到上千，如何对记录进行快速查找？在介绍之前，需要了解下数据页的结构：数据页包括七个部分，分别是文件头（File Header）、页头（Page Header）、最大最小记录（Infimum+supremum）、用户记录（User Records）、空闲空间（Free Space）、页目录（Page Directory）和文件尾（File Tailer）。页结构的示意图如下所示： 在每个数据页中，记录是以单向链表的形式进行存储的。单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。为了加快检索，于是引入分组：当插入数据的时候，将第一条记录作为第一个分组。从插入第二条开始，归为第二组，当第二组的数据条数超过一定限制的时候（比如4-8条）分裂为新的组，依次类推，最后包含最大记录的组归为最大组。最后将每组最后一条记录的偏移量存储起来形成页目录，每组的偏移量就是一个槽，有了页目录之后，对页内数据的查找就可以根据二分查找法去定位数据了，页目录结构如下图所示：