数据库索引就是使用B-树和B+树来实现的
为什么要创建B+树算法?
给出两个常用的SQL语句:
根据某个值查找数据:select*fromuserwhereid=;
根据区间值来查找某些数据:select*fromuserwhereidandid
考虑到性能方面的需求,主要是执行效率和存储空间
在执行效率方面,我们希望通过索引,查询数据的效率尽可能的高,在存储空间方面,我们希望索引不要消耗太多的内存空间.
平衡二叉查找树:虽然查找效率很高,时间复杂度为o(nlogn).而且对树进行中序遍历,可以得到一个从小到大进行排列的数据结构.但是并不支持按照区间快速查找数据.
我们可以通过改造二叉查找树来解决这个问题:
树中的节点并不存储数据本身,而只存储索引.除此之外,我们把每个叶子节点串在一条链表上,链表中的数据是从小到大有序排列的.下图为经过改造后的二叉查找树:
改造之后,如果我们需要求某个区间的数据.我们只需要拿区间的起始值,在树中进行查找,当查找到某个叶子节点后,我们再顺着链表往后遍历,直到链表中的节点数据值大于区间的终止值为止.所有遍历到的数据,就是符合区间值的所有数据.
但是,我们需要考虑到,要为几千万甚至上亿的数据构建索引,如果将索引存储再内存中,尽管内存的速度非常快,查询的效率非常高,但是,占用的内存会非常多.
我们可以借助以时间换空间的思路,把索引存储在硬盘中,而非内存中.但是硬盘的读取速度为毫秒级别,内存的访问速度是纳秒级别的,读取同样大小的数据,从磁盘中花费的时间是从内存中读取所花费的时间的上万倍,甚至几十万倍.严重影响到了查询效率.
二叉查找树,经过改造以后,就支持区间查找的功能了.不过为了节省内存,如果把树存储在硬盘中,那么每个节点的读取,都要经过一次磁盘操作.树的高度就为每次查询数据时,磁盘IO操作的次数.
那么一个优化方法就是减少树的高度,那么如何减少树的高度呢?答案是构建多叉树.
对于相同个数的数据构建m叉树索引,m叉树中的m越大,那么树的高度就越小,那么m叉树的m是不是越大越好呢?
内存和磁盘中的数据都是按页(一页大小通常为4kb)来读取的,一次会读取一页的数据,如果读取的数据量超过一页,就会触发多次io操作.所以,在选择m大小的时候,尽量让每个节点的大小等于一个页的大小.这样,读取一个节点,只需要一次磁盘io操作.
数据的写入会涉及到索引的更新,会导致写入变慢.对于一个b+树来说,m值是根据页的大小事先计算好的,也就是说,每个节点最多只能有m个子节点.在往数据库中写入数据的时候,有可能使得索引中某些结点的子节点个数超过m.造成读取一个节点的数据要进行多次磁盘IO操作.所以需要进行结点裂变.
同样在删除节点的时候,可能导致某些结点的个数过少,如果每个节点的个数都很少,会影响到索引的效率.于是设定了一个阈值.如果某个节点的子节点个数小于m/2,就将其与兄弟结点合并.
B+树的特点:
每个结点中子节点的个数不能超过m,也不能小于m/2.
根节点的子结点个数可以不超过m/2,这是一个例外.
m叉树只存储索引,并不存储数据.
通过链表将叶子节点串联到一起,方便区间查找.
一般情况,根节点存储在内存中,其他结点存储在磁盘中.
与B树区别:
B树结点存储数据
B树叶子节点不需要链表来串联
B+树中,将叶子节点串起来的链表,是单向链表还是双向链表?为什么?
对于B+tree叶子节点，是用双向链表还是用单链表，得从具体的场景思考。我想，大部分同学在开发中遇到的数据库查询，都遇到过升序或降序问题，即类似这样的sql:selectname,age,...fromwhereuidstartValueanduidendValueorderbyuidasc(或者desc)，此时，数据底层实现有两种做法：1）保证查出来的数据就是用户想要的顺序2）不保证查出来的数据的有序性，查出来之后再排序以上两种方案，不加思考，肯定选第一种，因为第二种做法浪费了时间（如果选用内存排序，还是考虑数据的量级）。那如何能保证查询出来的数据就是有序的呢？单链表肯定做不到，只能从头往后遍历，再想想，只能选择双向链表了。此时，可能有的同学又问了：双向链表，多出来了一倍的指针，不是会多占用空间嘛？答案是肯定的。可是，我们再细想下，数据库索引本身都已经在磁盘中了，对于磁盘来说，这点空间已经微不足道了，用这点空间换来时间肯定划算呀。顺便提一下：在实际工程应用中，双向链表应用的场景非常广泛，毕竟能大量减少链表的遍历时间
预览时标签不可点收录于话题#个上一篇下一篇