为什么B+树索引比顺序索引文件效率要高?
一、为什么B+树索引比顺序索引文件效率要高
B+树进化具有的优点
索引节点没有数据，比较小，能够完全加载到内存中而且叶子节点之间都是链表的结构，所以B+Tree也是可以支持范围查询的，而B树每个节点key和data在一起，则无法区间查找B+树中因为数据都在叶子节点，每次查询的时间复杂度是稳定的，因此稳定性保证了B+树的检索过程
我们再来看下B+树的检索过程
从B+树的根开始，逐层找到叶子节点。找到叶子节点为对应的数据页，将数据叶加载到内存中，通过页目录的槽采用二分查找的方式先找到一个粗略的记录分组。在分组中通过链表遍历的方式进行记录的查找。B+树页节点结构
将所有的记录分成几个组， 每组会存储多条记录，页目录存储的是槽（slot），槽相当于分组记录的索引，每个槽指针指向了不同组的最后一个记录我们通过槽定位到组，再查看组中的记录页的主要作用是存储记录，在页中记录以单链表的形式进行存储。
单链表优点是插入、删除方便，缺点是检索效率不高，最坏的情况要遍历链表所有的节点。因此页目录中提供了二分查找的方式，来提高记录的检索效率。所以B+树索引比顺序索引文件效率要高。
延伸阅读：
二、为什么要从AVL树变成B树
因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。
但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。
另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。
如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。
如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。
我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？
可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低
猜你喜欢LIKE
相关推荐HOT
更多>>
为什么要学IO模型?
一、要学IO模型的原因1、理解应用程序性能IO操作是网络应用程序中的关键部分，它涉及数据的输入和输出。了解不同的IO模型可以帮助开发人员更好...详情>>
2023-10-15 20:56:04
网站域名有www没有www区别?
一、网站域名有www没有www区别区别：主机记录也就是域名前缀不同，以aliyun.com为例网站域名带www：域名前缀为www，解析后的域名为www.iyun.com...详情>>
2023-10-15 17:02:21
gulp与webpack的区别?
一、gulp与webpack的区别gulpgulp强调的是前端开发的工作流程，我们可以通过配置一系列的task，定义task处理的事务（例如文件压缩合并、雪碧图...详情>>
2023-10-15 14:45:09
insmod 和 modprobe有什么区别?
一、insmod 和 modprobe的区别insmod和modprobe都是在Linux系统中加载内核模块的命令，它们之间的区别如下：1、命令格式不同insmod命令的语法格...详情>>
2023-10-15 14:09:11热门推荐
网站间隙性502怎么解决?
沸Python中动态编译函数compile参数filename的作用是什么?
热Mysql为什么只能支持2000w左右的数据量?
热为什么使用红黑树以及如何使用红黑树?
新HBase、TiDB、TDengine有什么优势?
为什么要学IO模型?
python中 from…import… 、from…import * 与import的区别?
AliSQL和OceanBase是什么关系?
APP开发的核心是什么?
什么是Sanity check，其作用是什么?
什么是Binder?
web前端开发学习路线?
Android开发手机APP软件需要做哪些准备?
网站域名有www没有www区别?
技术干货
京公网安备 11010802030320号