Skip to main content
Share Your Experience: Take the 2024 Developer Survey
17 votes
Accepted

Does mysql use B-tree,B+tree or both?

InnoDB uses B+Tree indexes, not B-Tree. All details about InnoDB data structures can be found here. You may also want to look at these diagrams. The author of both the resources, Jeremy Cole, was head ...
Federico Razzoli's user avatar
17 votes
Accepted

How is it possible for Hash Index not to be faster than Btree for equality lookups?

Disk based Btree indexes truly are O(log N), but that is pretty much irrelevant for disk arrays that fit in this solar system. Due to caching, they are mostly O(1) with a very large constant plus O((...
jjanes's user avatar
  • 40.1k
14 votes
Accepted

How do database operations (write, update, alter) on particular cell in a table are written to disk without overwriting entire file?

A very common misconception about Databases can be dispelled with this: Database != File When you update a Row in a database, the underlying data file on disk isn't touched at all - at least ...
Phill  W.'s user avatar
  • 8,805
13 votes

How is it possible for Hash Index not to be faster than Btree for equality lookups?

The why? issue is already addressed by other answers, but I question whether the premise is still correct. Things have moved on in Postgres since 9.6. Hash indexes are now first-class citizens (as ...
qris's user avatar
  • 341
10 votes

How is it possible for Hash Index not to be faster than Btree for equality lookups?

Hash lookup is theoretically an O(1) operation when the key hash maps directly to the physical location of the target record. The way it works in Postgres, if I understand it correctly, is a bit more ...
mustaccio's user avatar
  • 26.1k
10 votes
Accepted

Index seek to specific multi-column key, then get some rows in lexicographical order

What you are referring to is a row-comparison, and you are using it for a Keyset Pagination query. In DBMSs that support it, you can simply do where (col1, col2, col3) >= (@x1, @x2, @x3) SQL ...
Charlieface's user avatar
  • 13.2k
7 votes

Best index for jsonb in Postgres

GIN indexes do not work with any jsonb operators EXCEPT ? ?& ?| @>. Clearly, your use of comparison operators >= and <= are not on that list. And all of those operators that it could help ...
Evan Carroll's user avatar
  • 63.5k
6 votes
Accepted

How to enter records with keys to an initially empty B+ tree?

I think you have your page creation upside down. When a node splits it doesn't create more nodes down the hierarchy (son nodes in your nomenclature). Instead it creates more upwards, toward the root. ...
Michael Green's user avatar
6 votes

Index seek to specific multi-column key, then get some rows in lexicographical order

In a perfect world, people would be able to write queries in any logically-equivalent form and the optimizer would produce the same optimal execution plan in all cases. This isn't a practical ...
Paul White's user avatar
  • 85.7k
5 votes
Accepted

If a rowstore index is stored in a b-tree data structure, what kind of data structure is used for a columnstore index?

We usually think of an index as a way of rapidly finding all references to a given piece of information. In a textbook given a topic we can find all pages that mention that topic. In a database given ...
Michael Green's user avatar
5 votes

Is it possible to expose the max depth of the B-Tree behind a rowstore index or a way to see how many nodes were traversed for a particular query?

Some of this information like index depth can be found in DMF dm_db_index_physical_stats(). Some outer interesting information that can be found in it is number of used data pages and the ...
Peter Å's user avatar
  • 345
4 votes
Accepted

XML database for linux

I don't know much about graph database system and their capabilities but several traditional (SQL) database systems have options to store and manipulate XML documents: PostgreSQL: there is a XML data ...
ypercubeᵀᴹ's user avatar
4 votes
Accepted

Clustered Index Misunderstanding

some say, cluster index stores the whole records in deepest leaf of index. Yes this is correct. The leaf pages of the clustered index contain the actual table rows. This is the actual data. There is ...
Martin Smith's user avatar
  • 84.8k
4 votes

How many B-tree indexes do I need to support lookups by any subset of n columns?

Pushing theory aside a little, you are likely to see vanishing returns with wider and wider indexes so might be better to provide, for instance, just indexes on each two-column combination. Is a ...
David Spillett's user avatar
4 votes
Accepted

Pageinspect function bt_metap says 'index is not a btree index'

Because it is a partitioned index, not a regular index. Similar to partitioned tables, partitioned indexes don't hold any data, so it would not make sense to use them with pageinspect's functions. The ...
Laurenz Albe's user avatar
3 votes

Order of a 2-level b+tree with n-distinct (assume e.g. n=10) entries

The order of a B-Tree (and its various derivations, B+, B-link etc.) is the maximum possible number of child nodes. Since yours is a two-level tree calculating the order is the same as calculating the ...
Michael Green's user avatar
3 votes
Accepted

PostgreSQL covering index on large table as alternative to CLUSTER command

PostgreSQL does not have covering indexes. There has been some work on them, but it has not yet been accepted into the code tree. So there are limitations. If you have unique constraint on some ...
jjanes's user avatar
  • 40.1k
3 votes
Accepted

How to understand Composite Primary Key when it comes to storage (in Mysql)?

(This answer is focused on MySQL; in particular, the InnoDB Engine. JCole's blog (which you linked to) is valid for InnoDB, but might be overly technical. I'll try to give a lighter answer.) Think ...
Rick James's user avatar
  • 78.4k
3 votes

Containment check tstzrange @> timestamptz not using btree or gist index

The question is what is the reason the index is not used with the tstzrange containment operator and if there is a way to make it work. The reason is quite trivial. B-tree indexes do no support the ...
Erwin Brandstetter's user avatar
3 votes

Does mysql use B-tree,B+tree or both?

A B+Tree is a just a binary search tree, like a B-Tree, where, The leaves (buckets) have links to the right and left siblings buckets), making the tree an index into a linked list. Usually each ...
Evan Carroll's user avatar
  • 63.5k
2 votes

Multi-column btree index & INLJ

I very much doubt it will ever do that. PostgreSQL doesn't yet implement index skip scans, and if it did they would only be effective if there were only a handful of different actors. It is possible,...
jjanes's user avatar
  • 40.1k
2 votes

Can you use multiple types of indexes in one composite index

FULLTEXT and BTree cannot be mixed in a single composite index. Please provide SHOW CREATE TABLE and the SELECT for further discussion of alternatives. Always(?), the Optimizer will pick a FULLTEXT ...
Rick James's user avatar
  • 78.4k
2 votes

Query results not as expected - Jsonb Postgres

Try this.. Just out of curiosity.. CREATE INDEX idx_btree_ig_follower_count ON public.influencers USING BTREE (CAST(ig->>'follower_count' AS int)); Then in your query, cast to int. SELECT ...
Evan Carroll's user avatar
  • 63.5k
2 votes

Containment check tstzrange @> timestamptz not using btree or gist index

As far as my research goes, postgresql is not able to rewrite containment check into an expression that could be matched using btree index, i.e. esl1.created_at >= now() - interval '1 hour' AND ...
Gajus's user avatar
  • 1,195
2 votes

Offset vs Where performance for pagination with index

Yes, there is a performance difference, especially with big OFFSETs. With OFFSET you ORDER BY your indexed column, and then limit the result set by removing the first x rows indicated by OFFSET x. All ...
dbdemon's user avatar
  • 6,371
2 votes

PostgreSQL btree index for int with character varying (ILIKE) not working

varchar_pattern_ops with a btree index only works for patterns which do not start with a wildcard. So not for ilike '%PHP%', which does start with a wildcard. Multicolumn GIN indexes are not like ...
jjanes's user avatar
  • 40.1k
2 votes

Check int4range includes number using B-tree index

Since you have relatively few distinct values, there is an efficient solution with a B-tree index. Probably faster than a query based on the GiST index for more than a few result rows. The GiST ...
Erwin Brandstetter's user avatar
1 vote
Accepted

How does MySQL skip ranges (nodes) in a loose index scan?

I think the Optimizer works something like this: It can find the first row: MIN(name) WHERE foo=123 It can find the last row: MAX(name) WHERE foo=123 Those are done via a drill-down in the BTree, ...
Rick James's user avatar
  • 78.4k
1 vote

About the Index in MYSQL

they enforce the ordering of the rows of the table physically In fact most RDBMS do not order the results by default until ORDER BY is declared explicitly. Some ordered results can occure ...
Kondybas's user avatar
  • 4,448

Only top scored, non community-wiki answers of a minimum length are eligible