本文整理自网络,侵删。
目录
- 1. 多路搜索树
- 2. B树-多路平衡搜索树
- 3. B树索引
- 4. B+树索引
- 总结
如果用树作为索引的数据结构,每查找一次数据就会从磁盘中读取树的一个节点,也就是一页,而二叉树的每个节点只存储一条数据,并不能填满一页的存储空间,那多余的存储空间岂不是要浪费了?为了解决二叉平衡搜索树的这个弊端,我们应该寻找一种单个节点可以存储更多数据的数据结构,也就是多路搜索树。
1. 多路搜索树
1、完全二叉树高度:O(log2N)
,其中2为对数,树每层的节点数;
2、完全M路搜索树的高度:O(logmN)
,其中M为对数,树每层的节点数;
3、M路搜索树主要用于解决数据量大无法全部加载到内存的数据存储。通过增加每层节点的个数和在每个节点存放更多的数据来在一层中存放更多的数据,从而降低树的高度,在数据查找时减少磁盘访问次数。
4、所以每层的节点数和每个节点包含的关键字越多,则树的高度越矮。但是在每个节点确定数据就越慢,但是B树关注的是磁盘性能瓶颈,所以在单个节点搜索数据的开销可以忽略。
2. B树-多路平衡搜索树
B树是一种M路搜索树,B树主要用于解决M路搜索树的不平衡导致树的高度变高,跟二叉树退化为链表导致性能问题一样。B树通过对每层的节点进行控制、调整,如节点分离,节点合并,一层满时向上分裂父节点来增加新的层等操作来来保证该M路搜索树的平衡。
M为B树的阶数或者说是路数,在B树中,每个节点都是一个磁盘块(页)。每个非叶子节点存放了关键字和指向儿子树的指针,具体数量为:M阶的B树,每个非叶子节点存放了M-1个关键字和M个指向子树的指针。如图为5阶B树结构的示意图:
3. B树索引
首先创建一张user表:
create table user( id int, name varchar, primary key(id) ) ROW_FORMAT=COMPACT;
假如我们使用B树对表中的用户记录建立索引:
B树的每个节点占用一个磁盘块,磁盘块也就是页,从上图可以看出,B树相对于平衡二叉树,每个节点存储了更多的主键key和数据data,并且每个节点拥有了更多的子节点,子节点的个数一般称为阶,上述图中的B树为3阶B树,高度也会降低。假如我们要查找id=28
的用户信息,那么查找流程如下:
1、根据根节点找到页1,读入内存。【磁盘I/O操作第1次】
2、比较键值28在区间(17,35),找到页1的指针p2;
3、根据p2指针找到页3,读入内存。【磁盘I/O操作第2次】
4、比较键值28在区间(26,35),找到页3的指针p2。
5、根据p2指针找到页8,读入内存。【磁盘I/O操作第3次】
6、在页8中的键值列表中找到键值28,键值对应的用户信息为(28,po);
相关阅读 >>
更多相关阅读请进入《mysql》频道 >>
数据库系统概念 第6版
机械工业出版社
本书主要讲述了数据模型、基于对象的数据库和XML、数据存储和查询、事务管理、体系结构等方面的内容。
转载请注明出处:木庄网络博客 » MySQL中B树索引和B+树索引的区别详解
相关推荐
评论
管理员已关闭评论功能...