开发者社区> 数据库> 正文

B树和B+树索引原理

简介: B树和B+树原理及其在不同数据库系统中的应用。

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

一、B树和B+树

1.1 B树

B-Tree,即B树或者B-树。
1
一棵 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+树

2

m阶的b+树的特征:

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

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

1.3 总结

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

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

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

二、Oracle里的B树

4

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

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

上图ROWID:

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

三、MongoDB里的B树

5

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

四、MySQL里的B+树

2.1 MyISAM引擎索引实现

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

2.1.1 主键索引

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

2.1.2 辅助索引

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

2.2 InnoDB引擎索引实现

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

2.2.1 主键索引

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

2.2.2 辅助索引

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

参考:
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

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
上一篇:快照技术使用
+ 订阅

分享数据库前沿,解构实战干货,推动数据库技术变革

其他文章