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 enoughand 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. -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/
rbtree-0.5.gz
Description: Unix tar archive
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers