B树和B+树索引原理

2021-07-31 07:20:35

总结一下B树和B+树在不同是数据库系统中的应用。

一、B树和B+树

1.1 B树

B-Tree，即B树或者B-树。

一棵 m 阶的 B 树，需要满足下列条件：

1. 定义任意非叶子结点最多只有M个儿子，且M>2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]，向上取整；
4. 非叶子结点的关键字个数=儿子数-1；
5. 所有叶子结点位于同一层；
6. k个关键字把节点拆成k+1段，分别指向k+1个儿子，同时满足查找树的大小关系。

B树的一些特点：

1. 关键字集合分布在整颗树中；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束；
4. 其搜索性能等价于在关键字全集内做一次二分查找；

从上图可以看出，key 为 50 的节点就在第一层，B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。

1.2 B+树

m阶的b+树的特征：

1. 有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）;
2. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接;
3. 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字;
4. 通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点;
5. 同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。

由于B+树所有的 data 域都在根节点，所以查询 key 为 50的节点必须从根节点索引到叶节点，时间复杂度固定为 O(log n)。

1.3 总结

通过以上的叙述和上面这张图，基本可以知道B树和B+树的区别：

B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据；
B 树中的叶子节点并不需要链表来串联。

从定义上来说，B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，无法区间查找。
事实上，例如oracle、MongoDB这样使用B树的数据，肯定是可以范围查询的，因为他们使用的B树也是在叶子节点存储行的位置信息，数据在逻辑上是连续的。其实，B+树就是 B树的改进版。

二、Oracle里的B树

上图显示了oracle里的单个索引。底部的空框表示索引指针指向的关联表的块
上图DBA是：

database block address，是索引所在的物理文件位置。DBAs包含文件和块。文件是物理数据库文件，块是数据所在的块。使用DBA_EXTENTS视图，您可以看到DBA地址与哪个对象相关联。

上图ROWID：

ROWID包含object＃，file＃，block＃和row＃，其中file＃是物理数据库文件，block＃是数据所在的块，row＃是指向块的指针。ROWID表示行所在块中的唯一物理位置。

三、MongoDB里的B树

叶块包含键值列表和指向磁盘上文档位置的指针。
可以发现的是，MongoDB的B树索引很大程度上和oracle类似。
例如，如果需要访问“BAKER”的记录，我们首先会查询标题块。标题块将告诉我们以A到K开头的键值存储在最左边的分支块中。访问此分支块，我们发现以A到D开头的键值存储在最左边的叶块中。访问这个叶块，我们找到值“BAKER”及其相关的磁盘位置，然后我们将使用它来获取相关文档。

四、MySQL里的B+树

2.1 MyISAM引擎索引实现

在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

2.1.1 主键索引

MyISAM引擎使用B+树作为索引结构，叶节点的data域存放的是数据记录的地址。

2.1.2 辅助索引

上图是在Col2上建立一个二级索引。
同样也是一棵B+树，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+树搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分（可以发现和Oracle的B树类似）

2.2 InnoDB引擎索引实现

Innodb是索引组织表。在InnoDB中，表数据文件本身就是按B+树组织的一个索引结构（就是索引组织表），这棵树的叶节点data域保存了完整的数据记录。

2.2.1 主键索引

因为InnoDB的数据文件本身要按主键聚集（聚集索引），所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

2.2.2 辅助索引

首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

参考：
https://blog.toadworld.com/2017/05/08/how-oracle-b-tree-indexes-work
https://www.cnblogs.com/boothsun/p/8970952.html
https://blog.csdn.net/login_sonata/article/details/75268075
https://dzone.com/articles/effective-mongodb-indexing-part-1

码农公寓