Re: Free Space Map data structure
От | Hannu Krosing |
---|---|
Тема | Re: Free Space Map data structure |
Дата | |
Msg-id | 1207857885.6837.8.camel@huvostro обсуждение исходный текст |
Ответ на | Re: Free Space Map data structure (Hannu Krosing <hannu@krosing.net>) |
Ответы |
Re: Free Space Map data structure
|
Список | pgsql-hackers |
> BTW, I'm pretty sure I have figured out the method for storing minimal > required binary tree as an array, where adding each page adds exactly > one upper node. The node added is often not the immediate parent, but is > always the one needed for covering all nodes. > > I just have to write it up in an understandable way and then you all can > look at it and tell if it is something well-known from Knuth or Date ;) Find sample code attached: not optimal at all, meant as proof-of-concept. just run the file to see how it works, some comments in the beginning. currently it interleaves leaf and internal nodes, but it may be better for some uses (like seqscanning leaf nodes when searching for clustered pos) to separate them, for example having 1st 4k for lef nodes and 2nd for internal nodes. also, I think that having a fan-out factor above 2 (making it more like b-tree instead of binary tree) would be more efficient due to CPU caches, but it takes some more work to figure it out. Of course unless someone recognizes the algorithm and can point to textbook example ;) --------------- Hannu
Вложения
В списке pgsql-hackers по дате отправления: