本文共 1370 字,大约阅读时间需要 4 分钟。
数据库查询是数据库的最主要功能之一。最基本的查询算法就是顺序查找,这种复杂度为O(n)的算法在数据量很大时是性能很差的。
目前大部分数据库系统和文件系统都采用B-Tree或者B+Tree作为索引结构。
为了描述B-Tree,首先定义一条数据记录为一个二元组[key,data],key为记录的键值,对于不同的数据记录,key是互不相同的。data为数据记录除key外的数据。
由于B-Tree树的特性,在B-Tree中按照key检索数据的算法就为:一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上做了优化,增加了顺序访问指针
如上图所示:在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能索引以索引文件的形式存储在磁盘中(因为索引文件也有可能很大,所以将索引文件存放在内存中不现实,也没有必要),这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数
我们需要知道的是,从磁盘中读取数据时,都是按照磁盘块来读取的,并不是一条一条的读,如果我们能把尽量多的数据放进磁盘块中,那一次磁盘读取操作就会读取更多的数据,那我们查找数据的时间也会大幅度降低
所以在B-Tree的设计中,运用了计算机的局部性原理:当一个数据被用到时,其附近的数据也通常会马上被使用,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入了B+树是对B树的进一步优化。
相比较B树:转载地址:http://lqjmb.baihongyu.com/