文件系统和数据库是由于什么原因才选择B树或B+树建立?
来源:千锋教育
发布人:xqq
2023-10-18
推荐
在线提问>>
一、文件系统和数据库是由于什么原因才选择B树或B+树建立索引的
索引的目标是要找到数据所在的物理位置，因此用树去实现搜索数据所在物理位置，每个节点对应一次IO，因此结合知识点1为了减少搜索时间，就需要控制树的高度，那这样的话二叉树明显不行，因为二叉树插入的话树的高度是没办法控制的，因此采用B+树的形式，每个节点对应很多子节点，插入节点时增加子节点而不是增加树高度。更进一步，采用B+树时在相同数据量的情况下如何降低树的高度？当然是增加每一层的数据量，而考虑到知识点2，一个节点对应一个扇区大小存储多个数据项，既可以降低索引文件大小，又可以在相同数据量的情况下减少每层节点数，提高性能。
这是配合磁盘特性的，本来查询树使用多分支在内存里是没有意义的，只会导致读取了更多数据，但磁盘（或者说机械硬盘）的特性在于，多次随机读取效率远低于连续读取一大段数据，因为每一次都需要经过寻道。这样B树就被设计为用较少的次数读取磁盘，每次读取较大的块，从而优化整体查询。
延伸阅读：
二、使用B+树的好处
由于B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。
B+树的叶节点由一条链相连，因此，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间。
下一篇KEGG 怎么用?
