我们看一下常见的检索算法和数据结构。
循环遍历查找
从一组无序的数据中查找目标数据,常见的方法是遍历查询,n条数据,时间复杂度为O(n),最快需要1次,最坏的情况需要n次,查询效率不稳定。...示例:
从下列有序数字中查找数字9,过程如下
[1,2,3,4,5,6,7,8,9]
第1次查找:[1,2,3,4,5,6,7,8,9]中间位置值为5,9>5,将查找范围缩小至5右边的部分:[6、7、8...、9]
第2次查找:[6、7、8、9]中间值为8,9>8 ,将范围缩小至8右边部分:[9]
第3次查找:在[9]中查找9,找到了。...【磁盘I/O操作第3次】
在磁盘块8中的关键字列表中找到关键字29
分析上面过程,发现需要3次磁盘I/O操作,和3次内存查找操作,由于内存中的关键字是一个有序表结构,可以利用二分法快速定位到目标数据,而...n_owned范围控制在[4,8]内,能保证每个slot管辖的范围内数据量控制在[4,8]个,能够加速目标数据的查找,当有数据插入的时候,page directory为了控制每个slot对应块中记录的个数