On 2019-05-30 10:11:36 -0700, Will Hartung wrote:
> Well part of the problem is that “B-tree” is a pretty generic term. Pretty much
> every index is either some form of hash, or some form of tree. We use the term
> B-tree, even though pretty much no major index is actually a binary tree.
There seems to be no consensus on what the "B" stands for ("balanced"?
"Bayer"?), but it definitely isn't "binary". A B-tree is not a binary
tree.
> They almost always have multiple branches per node.
Yup. A B-tree is optimized for disk I/O and uses large (one or more disk
blocks) nodes with many children (and often a variable number to keep
the size of the block constant).
> It’s also important to note that over time, while we may use the term B-Tree
> generically, there are many specialized trees used today.
There are several variants of B-trees (B+, B*, ...), but B-tree is not a
generic term for any tree. A B-tree has specific characteristics.
https://en.wikipedia.org/wiki/B-tree#Definition follows Knuth's
definition.
> Historically, the conventional B+Tree is popular for database indexes. A B+Tree
> rather than relying on “nodes” per se, really is based on pages. Nodes alone
> tend to be too fine grained, so it’s a game of mapping the nodes to pages on
> disk.
In the case of a B-tree a node *is* a page (or block or whatever you
want to call it). A B-tree uses large nodes with many children, it
doesn't cluster small nodes together.
[...]
> In a GIN index, if you index “ABCDEF”, there will be a A node, B node, C node,
> D node, etc. (And, please, appreciate I am talking in broad brush generalities
> here for the sake of exposition, not specific details of implementation or
> algorithms). So, simply, by the time you get to the bottom of an index, all you
> find is the pointer to the data, not the actual key that got you there. The Key
> is the path through the tree.
You probably have generalized too much to answer Jeremy's question.
Firstly, the GIN index doesn't generally index single characters. It
uses some rule to split the field into tokens. For example, for a text
field, it might split the field into words (possibly with some
normalization like case-folding and stemming) for an int array it might
use the values in the array, etc.
Jeremy asked specifically about btree_gin. The docs don't state that
this index support ordered comparisons. This doesn't work if you split
the field, so my guess is that it doesn't. For a single column it's
basically a btree index with a more compact tid list. Dumping the
contents of the index if hd seems to confirm this. For a btree_gin index
spanning multiple columns I'm not sure. I would have expected each
field to be a token, but it looks like both are stored together. So
unless somebody more knowledgeable speaks up, I guess Jeremy will have
to read the source.
hp
--
_ | Peter J. Holzer | we build much bigger, better disasters now
|_|_) | | because we have much more sophisticated
| | | hjp@xxxxxx | management tools.
__/ | http://www.hjp.at/ | -- Ross Anderson <https://www.edge.org/>
Attachment:
signature.asc
Description: PGP signature
