count, sum, avg by range in log(n) time

考虑一下这样一个查询：

select count(*), sum(tax), avg(weight)

  from pepole

where id >= ${minid} && id < ${maxid};

 

怎样才能实现更小的时间复杂度？

 

一般情况下，最简单的方法就是遍历这个区间。但是这需要O(logn +m)的时间复杂度，其中m是区间长度，n是总记录数。

 

实际上，可以略增一点存储代价，对该查询实现O(logn)的时间复杂度。我以前写过一篇文章 ，可以对count(*)实现logn复杂度:

  count(*, minid, maxid) = rank(maxid) - rank(minid)

其中，rank(id) 表示该记录在整个表中的序号（排序名词）。这很容易理解。

 

如果要计算sum(x)或avg(x)，需要扩张一下，在每个结点中存储一个隐藏值，用来表示该以结点为根的子树的sum(x)值，那么，插入/删除/修改的代价也是O(logn)，计算sum(x),avg(x)的代价也是O(logn)。

 

 sum(x, minid, maxid) = node(maxid).hidesumx - node(minid).hidesumx

 avg(x, minid, maxid) = sum(x)/count(*, minid, maxid)

 

BekeleyDB中，可以实现 count(*) 的log(n)时间复杂度，因为它提供了类似rank()函数的功能，使用btree表，建表时提供DB_RECNUM标志。查询时，使用DBC::get，用DB_GET_RECNO flag：

DB_ENV** dbenv;
DB* db;
/*.....*/
db_create(&db, dbenv, 0);
db->open(db, NULL, "tablename", "filename", DB_BTREE, DB_CREATE, 0);
db->set_flags(db, DB_RECNUM);

/*.....*/

int get_rank(DB* db, const void* key, size_t klen, db_recno_t* rank)
{
	int  ret;
	DBC* curp;
	DBT  key = {0}, data = {0}, ignore = {0}, recno = {0};

	key.data = key;
	key.size = klen;
	recno.data = rank;
	recno.size = sizeof(*rank);

	ret = curp->get(curp, &key, &data, DB_SET);
	if (0 == ret) {
		ret = curp->get(curp, &ignore, &recno, DB_GET_RECNO);
	}
	return ret;
}