B+树,索引树

引言

时隔一年,我又想起当初看数据库时,看到的B+树,就是数据库的索引使用的数据结构。再整理一下,看看自己没有忘记很多吧。

概述

B+树之前,先来看一下二叉查找树(1,2,3,4,5,6,7)

恩, 差不多就长这样。诚然,在二叉查找树中查找某个元素是很快速的,二分查找嘛。但想想数据库查找数据的场景:

select * from user where id > 10, 显然,对于这种查找区间来说,二叉查找树并不高效。那么B+树是如何解决这个问题的呢?

试想一下,区间查找比较高效的数据结构是什么?数组,只要找到id为10的元素下标,那么之后的所有就都符合了。

那么把上面修改一下,让二叉查找树树的叶子节点直接指向数组的下标不就好了嘛。修改后结构如下:

这时,如果想找select * from user where id > 2 and id < 5, 那么,直接找到2的下标,然后向后遍历,到第一个>=5的值出现停止,之间是满足条件的数据。没错,这就是B+树。

这个结构是怎么想出来的我不知道啊,但是我今天突然发现,他的存储方式和跳表十分之像啊。莫非是受到了跳表的启发?亦或是跳表受到了B+树的启发?咱也不知道。

引申

很好,B+树整明白了,新的问题出现了。如果数据库使用这种数据结构存储,全部放到内存中肯定是不现实的,势必要将其存储到硬盘中,待查找时再到文件中读取。但如果放到文件中,势必会造成IO的缓慢,每次读取节点都访问文件,要是树到高度很夸张的话,光IO就要耗尽耐心了。

既然如此,那就降低IO好了,增加树每一层的节点数量,也就是二叉树变成n叉树(也确实是这么做的)。

算一下,如果是3叉树,高度为3(这个高度为索引树的高度),可索引的数组长度为:(3^4=81);如果是5叉树,高度为3,可索引数组长度为:(5^4=625);如果是100叉树,高度为3,可索引长度为:(100^4=1亿)。索引1亿的数据量,高度也只有3,意味着只要进行3此IO就可以定位到。完美。

那树进行分叉过多,是不是在每个节点搜索子节点的效率下降了?这里可以再使用一些查找算法降低时间复杂度。


以上就是我回忆的内容了,感觉并没有什么晦涩的,大部分是重新回忆了一遍。但是,温故而知新嘛。不知点新怎么好意思写出来。一下就是我最近才晓得的了。

B+树是不是分叉越多越好

那肯定不是越多越好啊,要是一层就把所有数据都存储了,要他还有什么用,根本没有起到快速定位的作用。

但我想说的并不是这。我们知道,操作系统在读取磁盘中的数据时,是按照页来读取和管理的,一页大小为4kb。当读取数据时,如果大小超过4kb,就会触发多次IO。4kb的大小,其实对于存储节点已经很大了。也就是说,我们每个节点的大小最好是<=4kb,否则就会触发多次IO。

但是,节点在更新时,势必会导致其大小改变。如何保证n叉树始终为n叉树呢?

添加节点

其实很简单,多了就拆呗。如果节点超出大小,就拆分成两个节点。但拆分后父节点不就多了么。那就父节点在拆,一直拆到根节点为止。如果根节点在超出大小,那就再拆,整个新的根节点出来。

删除节点

其实,删除节点不做处理也不会影响节点大小超出限制。但是,长此以往,可能会导致某些节点元素过少,严重影响查询效率。那么,如果节点内元素的数量小于n/2,就把相邻的两个节点合并为一个节点。那要是合并后元素数量超出大小呢?再拆呗。

本文分享自微信公众号 - 烟草的香味(hujing-bc),作者:胡靖哥哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构之跳表

    线性表中的链表是我们都很熟悉的结构了, 链表的增删优于数组, 但是不支持随机访问, 链表在查找时, 只能从头节点向后遍历, 那么针对链表, 能不能解决其访问效率...

    烟草的香味
  • 纠错码简介

    网络中的通信基于TCP和UDP两个通信协议, 这大家都知道的, 什么TCP的三次握手等等, 面试经常被问到. 三次握手是为了保证连接的正确建立. 但是, 在通信...

    烟草的香味
  • 基于redis的分布式锁

    1.如果在第一步之后, 程序崩了, 没有给锁设置过期时间, 导致所有后续操作都无法正常获取到锁. 怎么破?

    烟草的香味
  • 很短 | 图解 Raft 算法

    想象一下,我们有一个单节点系统,且作为数据库服务器,然后存储了一个值(假设为X)。然后,有一个客户端往服务器发送了一个值(假设为8)。只要服务器接受到这个值即可...

    芋道源码
  • 寻找红黑树的操作手册

    二叉树知识点回忆以及整理这篇文章中我们说过“二叉树是一个简单的二分查找,但其性能取决于二叉树的层数”。

    静默加载
  • 新手村:Redis 进阶篇三---主从复制

    前面几篇内容我们都是在一台 Redis 服务器上进行操作,包括数据的读、写以及备份操作。本篇要介绍的主从复制,是指将一台 Redis 服务器的数据,复制到其他 ...

    syy
  • Zookeeper入门

    爱撒谎的男孩
  • 通俗易懂的红黑树图解(下)

    回顾一下 通俗易懂的红黑树图解(上),上篇首先介绍了二叉树的定义以及二叉树的查找,然后介绍了红黑树的五点性质以及红黑树的变色、左旋以及右旋等操作,最后结合变色、...

    政采云前端团队
  • 数据结构之红黑树

      红黑树和红色和黑色这两种颜色有关,事实上,在红黑树中,对每一个节点都附着一个颜色,或者是红色或者是黑色。红黑树首先是一棵二分搜索树,这一点和AVL树是一样的...

    别先生
  • ES[7.6.x]学习笔记(二)ES的集群原理 ## 发现

    发现是节点之间彼此发现,形成集群的一个过程。这个过程发生的场景有很多,比如:你启动了一个集群节点,或者一个节点确认主节点已经挂掉了,或者一个新的主节点被选举了。

    小忽悠

扫码关注云+社区

领取腾讯云代金券