Thread: btree.sgml typo?
There is a sentence in btree.sgml: <productname>PostgreSQL</productname> includes an implementation of the standard <acronym>btree</acronym> (multi-way binary tree) index data structure. I think the term "btree" here means "multi-way balanced tree", rather than "multi-way binary tree". In fact in our btree, there could be more than one key in a node. Patch attached. Best regards, -- Tatsuo Ishii SRA OSS, Inc. Japan English: http://www.sraoss.co.jp/index_en.php Japanese:http://www.sraoss.co.jp diff --git a/doc/src/sgml/btree.sgml b/doc/src/sgml/btree.sgml index c16825e2ea..996932e35d 100644 --- a/doc/src/sgml/btree.sgml +++ b/doc/src/sgml/btree.sgml @@ -13,7 +13,7 @@ <para> <productname>PostgreSQL</productname> includes an implementation of the - standard <acronym>btree</acronym> (multi-way binary tree) index data + standard <acronym>btree</acronym> (multi-way balanced tree) index data structure. Any data type that can be sorted into a well-defined linear order can be indexed by a btree index. The only limitation is that an index entry cannot exceed approximately one-third of a page (after TOAST
On Sat, Jan 5, 2019 at 1:35 AM Tatsuo Ishii <ishii@sraoss.co.jp> wrote: > <productname>PostgreSQL</productname> includes an implementation of the > standard <acronym>btree</acronym> (multi-way binary tree) index data > structure. > > I think the term "btree" here means "multi-way balanced tree", rather > than "multi-way binary tree". In fact in our btree, there could be > more than one key in a node. Patch attached. +1 for applying this patch. The existing wording is highly confusing, especially because many people already incorrectly think that a B-Tree is just like a self-balancing binary search tree. There is no consensus on exactly what the "b" actually stands for, but it's definitely not "binary". I suppose that the original author meant that a B-Tree is a generalization of a binary tree, which is basically true -- though that's a very academic point. -- Peter Geoghegan
> On Sat, Jan 5, 2019 at 1:35 AM Tatsuo Ishii <ishii@sraoss.co.jp> wrote: >> <productname>PostgreSQL</productname> includes an implementation of the >> standard <acronym>btree</acronym> (multi-way binary tree) index data >> structure. >> >> I think the term "btree" here means "multi-way balanced tree", rather >> than "multi-way binary tree". In fact in our btree, there could be >> more than one key in a node. Patch attached. > > +1 for applying this patch. The existing wording is highly confusing, > especially because many people already incorrectly think that a B-Tree > is just like a self-balancing binary search tree. > > There is no consensus on exactly what the "b" actually stands for, but > it's definitely not "binary". I suppose that the original author meant > that a B-Tree is a generalization of a binary tree, which is basically > true -- though that's a very academic point. Any objection for this? If not, I will commit the patch to master and REL_11_STABLE branches (btree.sgml first appeared in PostgreSQL 11). Best regards, -- Tatsuo Ishii SRA OSS, Inc. Japan English: http://www.sraoss.co.jp/index_en.php Japanese:http://www.sraoss.co.jp
>> On Sat, Jan 5, 2019 at 1:35 AM Tatsuo Ishii <ishii@sraoss.co.jp> wrote: >>> <productname>PostgreSQL</productname> includes an implementation of the >>> standard <acronym>btree</acronym> (multi-way binary tree) index data >>> structure. >>> >>> I think the term "btree" here means "multi-way balanced tree", rather >>> than "multi-way binary tree". In fact in our btree, there could be >>> more than one key in a node. Patch attached. >> >> +1 for applying this patch. The existing wording is highly confusing, >> especially because many people already incorrectly think that a B-Tree >> is just like a self-balancing binary search tree. >> >> There is no consensus on exactly what the "b" actually stands for, but >> it's definitely not "binary". I suppose that the original author meant >> that a B-Tree is a generalization of a binary tree, which is basically >> true -- though that's a very academic point. > > Any objection for this? If not, I will commit the patch to master and > REL_11_STABLE branches (btree.sgml first appeared in PostgreSQL 11). Done. Best regards, -- Tatsuo Ishii SRA OSS, Inc. Japan English: http://www.sraoss.co.jp/index_en.php Japanese:http://www.sraoss.co.jp