Thread: Indexing - comparison of tree structures
Hi,
I compared two data structures realistically by time, after estimating big O. T-tree outperforms b-tree, which is commonly used, for a medium size table. Lehmann and Carey showed the same, earlier.
Can you improve indexing by this?
Understandably
Sascha Kuhl
Attachment
T-tree (and variants) are index types commonly associated with in-memory database management systems and rarely, if-ever, used with on-disk databases. There has been a lot of research in regard to more modern cache conscious/oblivious b-trees that perform equally or better than t-tree. What’s the use-case?
On Fri, May 24, 2019 at 5:38 AM Sascha Kuhl <yogidabanli@gmail.com> wrote:
Hi,I compared two data structures realistically by time, after estimating big O. T-tree outperforms b-tree, which is commonly used, for a medium size table. Lehmann and Carey showed the same, earlier.Can you improve indexing by this?UnderstandablySascha Kuhl
Jonah H. Harris
Where I can I find research on trees and indexing related to postgresql?
Sascha Kuhl <yogidabanli@gmail.com> schrieb am Mo., 27. Mai 2019, 11:14:
Can you bring me to the research showing b-tree is equally performant? Is postgres taking this research into account?Jonah H. Harris <jonah.harris@gmail.com> schrieb am Sa., 25. Mai 2019, 02:15:T-tree (and variants) are index types commonly associated with in-memory database management systems and rarely, if-ever, used with on-disk databases. There has been a lot of research in regard to more modern cache conscious/oblivious b-trees that perform equally or better than t-tree. What’s the use-case?--On Fri, May 24, 2019 at 5:38 AM Sascha Kuhl <yogidabanli@gmail.com> wrote:Hi,I compared two data structures realistically by time, after estimating big O. T-tree outperforms b-tree, which is commonly used, for a medium size table. Lehmann and Carey showed the same, earlier.Can you improve indexing by this?UnderstandablySascha KuhlJonah H. Harris
Dear moderator,
Regards
Sascha Kuhl
Sascha Kuhl <yogidabanli@gmail.com> schrieb am Mo., 27. Mai 2019, 16:07:
Would notSascha Kuhl <yogidabanli@gmail.com> schrieb am Mo., 27. Mai 2019, 16:06:To give you another fair hint: big O estimations would have revealed such a difference.Sascha Kuhl <yogidabanli@gmail.com> schrieb am Mo., 27. Mai 2019, 14:06:I understand that changing is never easySascha Kuhl <yogidabanli@gmail.com> schrieb am Mo., 27. Mai 2019, 13:52:You don't have to be rude: social communication is higher than looking and studying in a mailing list db. For me, at least;)Thanks for the direction and permission (I'm respectful with the work of others)Jonah H. Harris <jonah.harris@gmail.com> schrieb am Mo., 27. Mai 2019, 13:05:On Mon, May 27, 2019 at 5:14 AM Sascha Kuhl <yogidabanli@gmail.com> wrote:--Can you bring me to the research showing b-tree is equally performant? Is postgres taking this research into account?Not trying to be rude, but you've been asking rather general questions; our mailing list is archived, searchable, and probably a better use of everyone's time for you to consult prior to posting. Per your question, to my knowledge, there is no active work on changing our primary b-tree index structure, which is based on Lehman and Yao's b-link tree. Given the maturity of our current implementation, I think it would be rather difficult to improve upon it in terms of performance, especially considering concurrency-related issues.Jonah H. Harris
Hi, On 2019-05-27 12:40:07 +0200, Sascha Kuhl wrote: > Where I can I find research on trees and indexing related to postgresql? 1) Please respect the list style of properly quoting responses inline, and only responding to messages that are somewhat related to the previous content 2) You ask a lot of question, without actually responding to responses 3) Please do some of your own research, before asking questions. E.g. there's documentation about our btree implementation etc in our source tree. Regards, Andres
On Tue, May 28, 2019 at 11:37:54AM -0700, Andres Freund wrote: > 1) Please respect the list style of properly quoting responses inline, > and only responding to messages that are somewhat related to the > previous content > 2) You ask a lot of question, without actually responding to responses > 3) Please do some of your own research, before asking > questions. E.g. there's documentation about our btree implementation > etc in our source tree. In this case, you may find the various README in the code to be of interest. All index access methods are located in src/backend/access/, and nbtree/README includes documentation for btree indexes. -- Michael