Re: Red-black tree for GIN

2009/11/23 Teodor Sigaev <teodor(at)sigaev(dot)ru>:
> Hi there,
>
> attached is a patch, which contains implementation of a  red-black
> tree,  a self-balanced implementation of binary tree.  The main goal of
> this patch is to improve creation time of GIN index in the corner cases.
> While creation, GIN collects data in memory in binary tree until it
> reach some limit and then it flush tree to disk. Some data could
> produces unbalanced binary tree,  for example, sorted data, so the tree
> degenerates to the list with O(N^2) processing time (see thread
> http://archives.postgresql.org/pgsql-performance/2009-03/msg00340.php)
> ), which cause very slow index creation.  Tom has fixed that by limiting
> depth of tree  (committed to 8.3 and 8.4),  but we found it's not enough
> and propose to use red-black tree, which is very good for skewed data and
> has almost the same performance for unsorted data, see
> http://www.sai.msu.su/~megera/wiki/2009-07-27 and
> http://www.sai.msu.su/~megera/wiki/2009-04-03 for more information.
>
> Implementation of red-black tree has several currently unused  methods,
> but they will be used in next patches.

I did a quick read-through of this, and one question that immediately
occurred to me is that rbtree.c says that it is adopted from
http://algolist.manual.ru/ds/rbtree.php. But I'm not sure what
license that code is under, so I'm not sure whether it's OK for us to
use it.

My other question is as related to performance. Can you provide a
test case that shows the performance improvement with this patch?

...Robert