B树和B+树索引原理

南山123 2019-09-17

编程语言 MongoDB mysql innodb Oracle 数据库 索引 存储 myisam

总结一下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-树只需要一次磁盘

登录 后评论
下一篇
corcosa
12336人浏览
2019-10-08
相关推荐
数据库索引原理及优化
1568人浏览
2016-09-26 14:30:00
数据库索引原理及优化
2827人浏览
2016-09-26 14:30:00
数据库索引的实现原理
731人浏览
2017-08-01 15:16:00
mysql innodb索引原理
1427人浏览
2019-03-02 18:26:35
SQL Server索引原理解析
696人浏览
2018-07-10 12:08:00
百度研发面经
877人浏览
2018-09-14 14:28:40
数据库索引的实现原理
1075人浏览
2017-07-04 09:55:00
B树和B+树
789人浏览
2018-11-14 12:21:00
0
0
0
725