欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

为什么使用B+Tree索引?

程序员文章站 2022-08-08 17:41:30
BTree解决了磁盘IO的问题但没有解决元素遍历复杂的问题。 B+Tree的叶子节点用链指针相连,极大提高区间访问速度。 ......

什么是索引?

索引是一种数据结构,具体表现在查找算法上。


索引目的

提高查询效率

【类比字典和借书】

如果要查“mysql”这个单词,我们肯定需要定位到m字母,然后从下往下找到y字母,再找到剩下的sql。如果没有索引,那么你可能需要把所有单词看一遍才能找到你想要的。

去图书馆借书也是一样,如果你要借某一本书,一定是先找到对应的分类科目,再找到对应的编号,这是生活中活生生的例子,通用索引,可以加快查询速度,快速定位。


数据结构——树

为什么使用B+Tree索引?

二叉树

每个节点最多含有两个子树的树称为二叉树。


二叉查找树adt tree

左子树的键值小于根的键值,右子树的键值大于根的键值。

为什么使用B+Tree索引?

平衡二叉树avl tree

在符合二叉查找树的条件下,还满足任何节点的两个子树的高度最大差为1。

btree

btree也称为平衡多路查找树

b-tree是为磁盘等外存储设备设计的一种平衡查找树。

为什么使用B+Tree索引?

b+tree

b+tree是在b-tree基础上的一种优化

  • 非叶子结点只存储键值信息,不存储数据
  • 所有的叶子结点都有一个链指针
  • 数据记录都存放在叶子结点中

为什么使用B+Tree索引?


mysql默认使用b+tree索引

索引本身也很大,所以存储在磁盘中,需要加载到内存中执行。

故:索引结构优劣标准:磁盘i/o次数


btree是为了充分利用磁盘预读功能而创建出来的一种数据结构。

局部性原理和磁盘预读

局部性原理:当一个数据被用到,其附近的数据很可能会马上用到

磁盘预读:由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘i/o。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入主存。


为什么平衡二叉树无法利用磁盘预读功能而btree可以?

平衡二叉树也称为红黑数,在逻辑上是平衡二叉树,但是在物理存储上使用的是数组,逻辑上相近的节点可能在物理上相差很远。


btree如何利用磁盘预读功能?

将节点大小设为等于一个页,btree新建节点时,也是按照页为单位申请,同时计算机存储分配也是按页对齐,那么一个节点只需一次io就可以读取全部节点数据。

【如果节点大小和btree大小不对齐,那么同一页节点可能需要两次io读取】

综上所述,用b-tree作为索引结构效率是非常高的。


为什么b+tree比btree更适合作为索引结构?

btree解决了磁盘io的问题但没有解决元素遍历复杂的问题。

b+tree的叶子节点用链指针相连,极大提高区间访问速度。【比如查询50到100的记录,查出50后,顺着指针遍历即可】