文件系统和数据库是由于什么原因才选择B树或B+树建立?
一、文件系统和数据库是由于什么原因才选择B树或B+树建立索引的
索引的目标是要找到数据所在的物理位置，因此用树去实现搜索数据所在物理位置，每个节点对应一次IO，因此结合知识点1为了减少搜索时间，就需要控制树的高度，那这样的话二叉树明显不行，因为二叉树插入的话树的高度是没办法控制的，因此采用B+树的形式，每个节点对应很多子节点，插入节点时增加子节点而不是增加树高度。更进一步，采用B+树时在相同数据量的情况下如何降低树的高度？当然是增加每一层的数据量，而考虑到知识点2，一个节点对应一个扇区大小存储多个数据项，既可以降低索引文件大小，又可以在相同数据量的情况下减少每层节点数，提高性能。
这是配合磁盘特性的，本来查询树使用多分支在内存里是没有意义的，只会导致读取了更多数据，但磁盘（或者说机械硬盘）的特性在于，多次随机读取效率远低于连续读取一大段数据，因为每一次都需要经过寻道。这样B树就被设计为用较少的次数读取磁盘，每次读取较大的块，从而优化整体查询。
延伸阅读：
二、使用B+树的好处
由于B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。
B+树的叶节点由一条链相连，因此，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间。
相关推荐HOT
更多>>
单片机最小系统是什么?
单片机最小系统是什么单片机最小系统是指能够保证单片机能够正常工作，满足其基本功能需求的系统。一般情况下，它包括以下部分：电源电路：为单...详情>>
2023-10-16 23:32:48
Kafka、ActiveMQ、RabbitMQ、RocketMQ 有什么优缺点?
一、KafkaKafka是一个分布式的流处理平台，具有以下优点和缺点：优点：– 高吞吐量：Kafka能够处理高流量的消息，适合处理大规模数据流。– 可...详情>>
2023-10-16 23:02:36
什么样的软件算是功能安全软件?
功能安全软件是指在特定应用环境下，能够满足安全性要求的软件。这类软件在关乎人身安全、环境保护等关键任务的应用领域中起着至关重要的作用。...详情>>
2023-10-16 21:56:18
什么是字符串匹配算法?
什么是字符串匹配算法字符串匹配算法是用于在一个文本串中查找特定模式串的方法。它在计算机科学和信息检索领域中具有重要的应用。字符串匹配问...详情>>
2023-10-16 21:16:26热门推荐
单片机最小系统是什么?
沸Kafka、ActiveMQ、RabbitMQ、RocketMQ 有什么优缺点?
热工作站和塔式服务器有什么区别?
热什么样的软件算是功能安全软件?
新什么是字符串匹配算法?
什么是分治算法，和递归有什么关系?
国产编程语言木兰(ulang)是什么?
有什么好用的需求管理和bug管理工具?
Python语言除了爬虫scrapy外还有哪些优势?
PHP数组具的特性有哪些?
MySQL索引为什么能让查询效率提高?
人工智能中图神经网络GNN是什么?
Web渗透文件上传有哪些漏洞?
数据量很大，逻辑不能在内存里做怎么办?
技术干货
京公网安备 11010802030320号