文件系统和数据库是由于什么原因才选择B树或B+树建立?
一、文件系统和数据库是由于什么原因才选择B树或B+树建立索引的
索引的目标是要找到数据所在的物理位置，因此用树去实现搜索数据所在物理位置，每个节点对应一次IO，因此结合知识点1为了减少搜索时间，就需要控制树的高度，那这样的话二叉树明显不行，因为二叉树插入的话树的高度是没办法控制的，因此采用B+树的形式，每个节点对应很多子节点，插入节点时增加子节点而不是增加树高度。更进一步，采用B+树时在相同数据量的情况下如何降低树的高度？当然是增加每一层的数据量，而考虑到知识点2，一个节点对应一个扇区大小存储多个数据项，既可以降低索引文件大小，又可以在相同数据量的情况下减少每层节点数，提高性能。
这是配合磁盘特性的，本来查询树使用多分支在内存里是没有意义的，只会导致读取了更多数据，但磁盘（或者说机械硬盘）的特性在于，多次随机读取效率远低于连续读取一大段数据，因为每一次都需要经过寻道。这样B树就被设计为用较少的次数读取磁盘，每次读取较大的块，从而优化整体查询。
延伸阅读：
二、使用B+树的好处
由于B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。
B+树的叶节点由一条链相连，因此，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间。
猜你喜欢LIKE
相关推荐HOT
更多>>
RESTful API的命名有什么讲究?
一、RESTful API的命名有什么讲究和目录没关系，通常是框架路由接管的 request uri解析出来的（v1、v2有可能是实际的目录）restful规范/资源名/...详情>>
2023-10-18 23:56:05
文件系统和数据库是由于什么原因才选择B树或B+树建立?
一、文件系统和数据库是由于什么原因才选择B树或B+树建立索引的索引的目标是要找到数据所在的物理位置，因此用树去实现搜索数据所在物理位置，...详情>>
2023-10-18 22:55:19
mysql如果单表数据量过千万怎么办?
一、mysql如果单表数据量过千万怎么办方案概述方案一：优化现有mysql数据库。优点：不影响现有业务，源程序不需要修改代码，成本最低。缺点：有...详情>>
2023-10-18 22:33:40
数据库表名、字段名用中文有什么问题?
一、数据库表名、字段名用中文的问题1、兼容性问题某些数据库管理系统（DBMS）可能不支持使用中文作为表名和字段名，或者对于中文的支持有限。...详情>>
2023-10-18 21:09:43热门推荐
RESTful API的命名有什么讲究?
沸KEGG 怎么用?
热文件系统和数据库是由于什么原因才选择B树或B+树建立?
热mysql如果单表数据量过千万怎么办?
新什么情况下需要使用分布式数据库?
为什么Cassandra的写速度比MySQL快?
数据库表名、字段名用中文有什么问题?
数据库文件存放在NAS中，会有什么问题吗?
多线程并发访问数据库中不同记录时应该采用什么办法?
为什么mysql要额外加入一个utf8mb4数据类型，而不是原地升级utf8?
PolarDB-X与PolarDB的关键区别是什么?
Mysql、SQLite、Mongo的区别?
为什么用Go语言做Web应用开发框架?
什么是i.MXRT11xx上的串行NOR Flash双程序可交替启动?
技术干货
京公网安备 11010802030320号