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：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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; } |
