idea's blog

排序的集合(Zset, SortedSet)是这样的一种集合数据结构, 集合中的元素不可重复, 而且元素之间根据每一个元素的权重来排序. Zset 是一种非常重要和应用广泛的数据结构, 是 Redis 数据库所支持的最核心一种. Zset 可用于排行榜, 好友列表, 去重, 历史记录等业务需求. 你可以理解一个 Zset 是一个下面结构的数据库表:

item,   score
UNIQUE, INDEX(int)

Item 列被加了 UNIQUE 约束, 所以可以去重. Score 列是加了索引的整数列, 可用于排序.

如果要在内存中实现一个 Zset 数据结构, 我们可以看 Redis 的源码.

Redis 用两个数据结构的组合来实现 Zset: Hashmap 和 Skiplist. Hashmap 存储的是元素对应 Redis 对象, 所以可以去重; Skiplist 用于排序. 虽然思路很简单, Redis 的实现代码量也不多, 但是要抽取出来使用也不是很方便. 所以, 我们可以实现一个简化版.

我用 C++ 来实现, 用到了 STL 容器, 代码量不过百行(不完全接口), 被应用在 SSDB 数据库的 key 过期功能上.

同样, 我也是用了两个数据结构, 不过是 std::map 和 std::set. map 用于去重, set 用于排序. 因为 STL 的 set 是排序的, 而且可以使用自定义的排序比较函数, 所以用起来非常方便. 当然, 你可以把 set 按成 map, 就可以实现 SortedHashmap 了.

class SortedSet
{
public:
	int size() const;
	int add(const std::string &key, int64_t score);
	int del(const std::string &key);
	// key will be pointed to the first time if SortedSet not empty
	int front(const std::string **key, int64_t *score=NULL) const;
	// the first item is copied into key if SortedSet not empty
	int front(std::string *key, int64_t *score=NULL) const;
	int pop_front();

private:
	struct Item
	{
		std::string key;
		int64_t score;
		
		bool operator<(const Item& b) const{
			return this->score < b.score
				|| (this->score == b.score && this->key < b.key);
		}
	};
	
	std::map<std::string, std::set<Item>::iterator> existed;
	std::set<Item> sorted_set;
};

具体的实现代码见: https://github.com/ideawu/ssdb/blob/master/src/util/sorted_set.cpp

Related posts:

1. 在有序的KV引擎之上建造结构化数据库引擎
2. SSDB在大数据量日志分析中的应用案例
3. 如何使用SSDB的zscan命令
4. Redis 导数据的 PHP 脚本
5. C++ const& 的坑