搜索:btree

B树

原创 2018-07-23 17:40 阅读(174)次
大规模数据存储中,实现索引查询是在这样一个实际背景下,树单个节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下(为什么会出现这种情况,因为磁盘的操作费时费资源,如果过于频繁的多次查找势必效率低下,详见磁盘读取数据的原理)。 根据磁盘查找存取的次数往往由树的高度所决定,所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,那么是不是便能有效减少磁盘查找存取的次数呢?那这种有效的树结构是一种怎样的树呢? 在无法减少查询需求(数据量)的情况下,那么如何减少树的深度,...