0%

STL中红黑树的用法探究及使用红黑树进行多字段索引的方法

STL中红黑树的用法探究及使用红黑树进行多字段索引的方法

前言

最近在造轮子,需要造分析型数据库。在关于热数据的设计中,对于到来的每一条热数据,我需要使用红黑树来维持热数据在内存中的有序索引。后来使用了STL中的红黑树,这个过程遇到了一大堆坑,网上能找到的资料又很少,所以记录了一下。

问题

我需要维护多个字段的索引,比如这么一张图,我需要在红黑树上维护对于b、c、d三个字段的索引:

图源https://www.zhihu.com/question/304037770/answer/1287557228

上图出自知乎问题mysql联合索引的B+树到底张什么样子啊?下@Limit的一个回答,这是innodb引擎下使用B+树的解决方法。但由于我现在维护的是热数据,并不需要进行磁盘IO,且只需要支持查询和插入的操作,所以我需要用红黑树来解决此问题。

过程

我看了一些项目中的红黑树,比如Nginx、Redis、Linux中的红黑树,这些红黑树都是使用c语言写的,和c++代码风格迥异,后来我就想到了STL中的红黑树。STL中的map、set、multiset等容器的底层实现都是红黑树嘛,所以STL内当然也是有红黑树的代码了。

C++ STL源码剖析之红黑树C++ STL源码剖析之set与multiset那些事这两篇文章帮了我很多,在第一篇文章的最后,作者提到了STL中红黑树的使用方法:

引入头文件:

1
>#include<map>或者<set>

类定义:

1
>_Rb_tree<int, int, _Identity<int>, less<int>> itree;

然后调用相应函数即可。

其中有一些很关键的方法,比如插入操作:
插入操作

其中与equal相关的方法,适用于红黑树中允许出现相同key值的情况,比如STL中的multiset;而unique相关方法适用于红黑树中不允许出现相同键值的情况,比如map或者set。

而带有下划线的方法,很容易让人联想到类中私有函数的命名规则。他们是函数内部实现用到的,因此我们不需要调用带有末尾下划线的方法。

1
2
3
4
5
6
7
8
9
10
11
_Rb_tree<int, int, _Identity<int>, less<int>> itree;

itree._M_insert_equal(3);
itree._M_insert_equal(4);
itree._M_insert_equal(1);
itree._M_insert_equal(2);

for (auto it = itree.begin(); it != itree.end(); it++)
{
cout << *it << endl;
}

输出结果:

1
2
3
4
1
2
3
4

使用迭代器对map遍历的过程、或者说对红黑树遍历的过程,实际上是对红黑树做中序遍历,输出的顺序自然是从小到大的排列顺序。

剩下的还有一些方法,比如find、erase之类的,都和其他STL容器的用法差不多,不再赘述。

上面只是最基本的红黑树用法,但实际上我们完全不知道_Rb_tree实例化时那一大堆模板参数的含义,就直接拿来用了,下面分析这些模板参数的含义。

首先看STL源代码中的:stl_tree.h

其中红黑树的模板参数定义如下,一共有5个模板参数:

1
2
3
4
5
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc = allocator<_Val> >
class _Rb_tree
{
........

在类的public定义中的typedef告诉了我们,前两个参数的含义其实是key和value:

key和value

第三个参数_KeyOfValue的含义花了我一整个上午和下午的时间才弄懂。其实_KeyOfValue通过重载函数调用运算符,即(),规定了通过value取得key的方式。

注意这里的key和value和map中的key和value很类似,但是稍微有些不同。我一开始就用map中的key-value的方式理解红黑树的key和value,导致代码一直编译不过。

这里红黑树的key其实是包含在value里面的,而map中的key和value是分开的。这么说可能有点抽象,举个例子,如果我们定义了一个map实例:

1
std::map<int, char> m;

那么在map中key就是int类型的,而value是char类型的,而在这个map底层的红黑树,它的key和value(也就是红黑树的前两个模板参数_Key_Val)将会是intpair<int, char>

这点我们可以通过阅读map的源代码(stl_map.h)发现:

map中的模板参数

std::map<int, char>的参数就会如上图所示,然后接下来我们再观察map实例化红黑树所用的模板参数。

首先注意这里对value_type的定义,std::map<int, char>value_type将会是std::pair<int, char>

value_type

然后在下面就是map中对红黑树的定义:

map对红黑树的定义

注意这里传入的是pair,而不是char本身。所以说红黑树的key是包含在value中的。我在这个地方被坑了好久,一直以为这里的key-value定义和map中一样,导致代码一直编译不过。

既然我们知道key是包含在value中的了,那么第三个参数_KeyOfValue其实就规定如何从value中取得key的过程。我们看回最初的那个红黑树的定义:

1
_Rb_tree<int, int, _Identity<int>, less<int>> itree;

这里第三个参数使用了_Identity,是什么意思呢?其实_Identity是“stl_function.h”中定义的一个结构体:

_Identity

其中的unary_function是一个结构体,它定义了一个二元运算的输入类与输出类:

1
2
3
4
5
6
7
8
9
10
11
12
/**
* This is one of the @link functors functor base classes@endlink.
*/
template<typename _Arg, typename _Result>
struct unary_function
{
/// @c argument_type is the type of the argument
typedef _Arg argument_type;

/// @c result_type is the return type
typedef _Result result_type;
};

但其实这里可以不去管unary_function,因为它的出现与否和红黑树没啥关系。我们要的其实是_Identity中的重载函数调用运算符(即对()的重载)。_Identity中对()进行了重载,最终的结果就是,返回了传入的参数本身。那么

1
_Rb_tree<int, int, _Identity<int>, less<int>> itree;

中的_Identity的含义其实就很明显了,他的意思就是,当我们插入1:

1
itree._M_insert_equal(1);

那么实际上1本身既是key也是value(map中的value含义)。注意红黑树中的key用于对节点进行排序,而value则是我们要存储的值。

我们回到map中对第三个模板参数的定义:

1
2
typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
key_compare, _Pair_alloc_type> _Rep_type;

这里第三个模板参数用的是: _Select1st,我们不妨看一下它的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
  template<typename _Pair>
struct _Select1st
: public unary_function<_Pair, typename _Pair::first_type>
{
typename _Pair::first_type&
operator()(_Pair& __x) const
{ return __x.first; }

const typename _Pair::first_type&
operator()(const _Pair& __x) const
{ return __x.first; }

#if __cplusplus >= 201103L
template<typename _Pair2>
typename _Pair2::first_type&
operator()(_Pair2& __x) const
{ return __x.first; }

template<typename _Pair2>
const typename _Pair2::first_type&
operator()(const _Pair2& __x) const
{ return __x.first; }
#endif
};

上面的unary_function与红黑树无关,可以不管,只看对运算符的重载。仔细一看会发现,其实他就是传入一个pair,然后return pair.first,仅此而已。我们前面说到第三个模板参数其实是规定了从value中取出key的过程,当我们使用map<int,char>时,获得key的过程其实就是从pair<int,char>中取出第一个数的过程。

_Select1st,自然也就有_Select2nd,_Select2nd的操作当然就是取出第二个元素。这样一来第三个模板参数_KeyOfValue就很清晰了,他其实就是一个结构体,然后对()运算符进行了重载,规定了从value中取出key的方法。当你在STL的源代码中看到

1
_KeyOfValue()(value)

其实就是通过value获取key的过程了。注意,如果要自己写第三个模板元参数,那么在重载()符号时,记得返回值必须是const类型的引用,比如const int&,关于这点可以参考:https://www.cnblogs.com/sandychn/p/12334194.html ,这篇文章也帮了我很多。

最后是第四个参数:_Compare

1
2
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc = allocator<_Val> >

顾名思义,这个参数自然和大小比较有关:当我们使用:

1
_Rb_tree<int, int, _Identity<int>, less<int>> itree;

其实这里的 less就是类似前面说的那些结构体,重载了()运算符,传入两个参数a、b,返回 a < b的布尔值。

回头再看看map的源代码,可以看到map的默认大小比较方法其实也是less:

less

附上less的代码,参考前面所说的,这里应该不难看懂:

1
2
3
4
5
6
7
8
/// One of the @link comparison_functors comparison functors@endlink.
template<typename _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};

当然这里我们也可以自己写一套大小比较逻辑。

红黑树的最后一个参数_Alloc和内存分配有关,一般我们保持其默认值就可以了。

至此,我们分析了红黑树实例化时不同模板元参数的含义,现在我们可以试试解决文章最开头提出的问题:

怎么在红黑树上构建图中所示b、c、d字段的索引:

图源https://www.zhihu.com/question/304037770/answer/1287557228

解决问题

根据我们分析的内容,我们首先需要一个结构体来存储上述所示的三个索引值:

1
2
3
4
5
6
7
8
9
10
struct keys
{

int a;
int b;
int c;

keys(int a, int b, int c)
: a(a), b(b), c(c){};
};

然后自定义一套比较规则:优先比较a、其次比较b、最后比较c,所以我简单地写了一大堆很笨的嵌套if:

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
27
28
29
30
struct my_less
{
bool
operator()(const keys &x, const keys &y) const
{
if (x.a < y.a)
return true;

else if (x.a > y.a)
return false;

else
{
if (x.b < y.b)
return true;

else if (x.b > y.b)
return false;

else
{
if (x.c < y.c)
return true;

else
return false;
}
}
}
};

然后就可以实例化一个类了:

1
2
3
4
_Rb_tree<const keys, 
pair<const keys, std::string>,
_Select1st<pair<const keys, char> >,
my_less > itree;

然后把我们前面的参数插入进去:

图源https://www.zhihu.com/question/304037770/answer/1287557228

1
2
3
4
5
6
7
itree._M_insert_unique(pair<const keys, string>(keys(13,12,4),"dll"));
itree._M_insert_unique(pair<const keys, string>(keys(1,5,4),"doc"));
itree._M_insert_unique(pair<const keys, string>(keys(13,16,5),"img"));
itree._M_insert_unique(pair<const keys, string>(keys(12,14,3),"xml"));
itree._M_insert_unique(pair<const keys, string>(keys(12,14,3),"txt"));
itree._M_insert_unique(pair<const keys, string>(keys(13,16,1),"txt"));
itree._M_insert_unique(pair<const keys, string>(keys(5,3,6),"pdf"));

最后使用迭代器遍历输出:

1
2
3
4
5
for (auto it = itree.begin(); it != itree.end(); it++)
{
std::cout << (*it).first.a << ' ' << (*it).first.b << ' '
<< (*it).first.c << ' ' << (*it).second << std::endl;
}

输出结果:

1
2
3
4
5
6
1 5 4 doc
5 3 6 pdf
12 14 3 xml
13 12 4 dll
13 16 1 txt
13 16 5 img

最后的结果完全我想要的顺序:优先按第一个索引排列,相同值看第二个索引,以此类推。

这部分内容坑了我好久,在网上能找到的资料也不多,所以我把这个过程记录下来了,感谢给我提供思路的那些文章和回答。

参考资料

C++ STL源码剖析之红黑树 - Francis的文章 - 知乎

C++ STL源码剖析之set与multiset那些事 - Francis的文章 - 知乎

mysql联合索引的B+树到底张什么样子啊? - Limit的回答 - 知乎

STL中_Rb_tree的探索

本文地址: https://www.chimaoshu.top/STL中红黑树的用法探究/
版权声明:本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议,转载请注明出处。

Welcome to my other publishing channels