目录:
🚀1.B树
🚀2.B+树
索引背后的数据结构是啥呢,是B+树,是为了数据库索引设计的,我们可以先了解B树,再说B+树
1.什么是B树
B树也叫B-树,这里的-不读减,是一个符号
我们已经学过了二叉搜素树,B树其实就是N叉搜素树,二叉搜索树只能在每一个结点放一个key,所以树的高度就很高,而N叉搜索树一个结点可以放多个key,高度大大降低,现在通过画图的形式来进行理解
这就是一个B树,结点的子树越多,那么树的高度就越低,树的高度越低,那么访问硬盘的次数就越少,这有利于提高查询效率
什么是B+树
B+树也是N叉搜索树,其实有点像,但是还是有区别的,继续画图来看
观察这个树,子结点中含有每个结点key的值
那么在查询的时候是以一个范围进行查询,B+树的最后一层的结点可以连接成一个单链表
如下图
就算查的数字在这个树里没有,那么只要通过范围圈出链表的一个范围即可
B+树实现了数据库的索引,那么举个例子,假如要插入一个学生,有id,name,number,address,等,
在B树中就相当于每一个结点的key值中存着这一行数据,比如30,就存着这个学生的所有数据,那么假如就要查30,就查到第一层就可以了,
如果是B+树,那么除了最后一层的结点是存储完整数据的,其他结点是不存该学生的所有信息的,只会存ID,那查询的时候必须查到最后一层才能拿到完整的数据
那么如果没有id ,那就不能使用索引了,因为使用B+树的前提是可比较的key值
在这个结构中,默认是id作为表主键的,
那么如果一个表里有多个索引呢,id是主键索引,那么针对name 也有一个索引
在建造B+树的时候还是按照id为主键建的,在叶子结点中有所有数据
针对name 这个索引,我们需要再创建一个B+树,这个树的叶子结点不保存完整数据,只保存id,在根据name查询的时候,只能查到id,还需要到以id为主键为索引创建的B+树中,再次查询,查到这个树里的叶子结点,才可以查到完整数据
这就叫回表过程,是由mysql自动完成的.
B+树就是mysql组织数据的方式
一张表的结构可能是表结构,也可能是树结构,取决于有没有索引,以及数据库使用的存储引擎
说了这么多,来总结一下
先来说一下B+树的特点
1.一个结点,可以存储N个key,N个key划分N个区间(B树划分的是N+1个区间)
2.每个结点的key的值都会在叶子结点中存在
3.B+树的叶子结点是首尾相连的,类似链表
4.只会在叶子结点上存储完整的行数据,非叶子结点只有key值
现在来说一说B+树的优点
1.一个结点可以存更多的key值,那么树的高度更矮,减少访问硬盘次数
2.所有的查询都会落到叶子结点上(访问的IO次数是一样的,这里的IO次数是指硬盘访问次数)
3.B+树的所有叶子结点构成一个链表,方便范围查询
4.完整的数据都存在叶子节点上,非叶子结点只会存储key,这些非叶子结点可能会存储在
内存中,那么又进一步减少了硬盘访问次数
B树的特点
1.一个结点可以存N个key值,N个key划分N+1个区间
2.每个结点都存储完整的行数据
3.每个结点的key的值在叶子结点中不会出现
4它的叶子结点不存在首尾相连的链表关系
B树的优点
1..一个结点可以存更多的key值,那么树的高度更矮,减少访问硬盘次数
2.所有的查询会落到每一个结点上,查询的速度也很快
今天的讲解就到这里,我们下期见
