3

So i was reading MySQL innoDB, which apparently stores table data by default on a clustered Index (b+tree) based on primary key, and the tuples are in the leafs of that b+tree

https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/

i was wondering do all the famous Relational DBMSes like PostgreSQL, Oracle, SQL server, SQLite, store it the same way? by making a clustered Index (b+tree) based on primary key and store data on the leafs of tree?

and does Clustered index on primary key in databases basically mean storing the table based on primary key on a B+tree table?

(sorry if this is a general question but i cant make 4-5 seperate questions asking the same for each of the databases i mentioned, if you only know about one or few of them please tell)

also if its a database does not use clustered by default, can you explain how does it structure the files, for example do they make a b+tree on primary key which the leafs point to some sort of address inside a heap or...?

EDIT :

so far we got the answers for all of them except SQLite, if anyone have any info on how tables are actually stored in SQLite by default please do tell.

11

Do all the famous Relational DBMSes like PostgreSQL, Oracle, SQL server, SQLite, store it the same way? by making a clustered Index (b+tree) based on primary key and store data on the leafs of tree?

No, not all. Lets take them one by one:

  • MySQL. MySQL has several "engines" and depending on what engine a table is defined to use, the storage is:

    • InnoDB: Yes, what you describe, the table data is stored in a clustered index, with the index based on the primary key columns on the table (and if there isn't a PK defined, on the first UNIQUE index with non-null columns and in the lack of that, on a secret 6-byte internal column).
    • MyISAM: No, the table is a heap, not a clustered index.
    • other engines: (NBD, Blackhole, CSV, etc) No, I think none of them uses a clustered index (except maybe NBD, not sure)
    • TokuDB: Yes. Similar to InnoDB but you may define more than one clustered indexes!
  • SQL Server: Yes, the default behaviour for tables that have a PK is to be clustered on the PK. This can be overridden though by declaring that the PK is NONCLUSTERED. You can also define another index (not the PK) to be the clustered index of the table. If the PK is deined as NONCLUSTERED and none of the indexes is defined as CLUSTERED, then the table is a heap. In recent versions, a 3rd option was added (besides clustered index and heap): columnstore which is a different way of organizing the table data.

  • PostgreSQL: No. All the tables are heaps, period. You can create additional indexes of various types (btree, hash, gin, gist, brin, etc) but the table data are stored in a heap.

  • Oracle: No. By default the tables are heaps unless created as Index Organized Tables (Oracle's term for clustered indexes).


Additional clarifications about table data organization:

  • Clustered Index: There is a btee+ index - based on some column(s) - and the leafs contain the table's data.

  • Heap: There is no btree index for the heap (other indexes like the PK may still use a btree). The data are stored as unordered lists of records. When a new row is inserted, it is usually added in a disk page with available space. Rows are referenced by some special Page/RowID (the details are implementation dependend and surely differ from DBMS to DBMS), so other indexes will include this reference.

  • Columnstore: Types of structure where data are stored as columns rather than rows.

Some more details can be found in the documentation of each DBMS and in: - Wikipedia: Database Storage Structures - Wikipedia: Columnstore databases

3

Db2 for Linux, Unix, Windows: No

In Db2 indexes that enforce row data location within the table ("heap") are commonly called clustering, not clustered. They don't contain row data*, only key values, and point to the actual row locations within the table. When rows are inserted, the data manager tries to place them on the page with other rows containing the same key value. If it is not possible, the rows will be added following the usual free space search logic. As a result, over time the table's cluster factor (the percentage of rows in the table ordered according to the clustering index) deteriorates. A REORG command is then used to restore clustering order by moving rows around.

There is no default clustering index in Db2 for LUW; you have to explicitly create one with the CLUSTER option.

Db2 for z/OS: No

Same as in Db2 for LUW, a clustering index does not contain row data* and simply points to the actual table rows. Row insert behaviour is the same as well.

In contrast to Db2 for LUW, if a clustering index is not explicitly declared, the very first index created on the table is implicitly taken to be clustering.

Db2 for i: Sort of

There is no clustering (or clustered) index concept in Db2 for i. However, when creating an index you have an option of adding all table columns to the index b-tree, some of the columns, or only key columns. The first option effectively creates a SQL Server-style clustered index, although table rows remain also stored separately in the table "heap".


*Unique indexes have the INCLUDE option that allows you to put individual non-key column values in the index itself, thus facilitating index-only access. In the extreme case of adding all non-key table columns to the primary key index you will end up with the index similar to the MS SQL Server clustered index.

1

Regarding SQL Server, the following behaviour is documented and is still valid from 4.2 to 2019 versions:

PRIMARY KEY and UNIQUE constraints

When you create a PRIMARY KEY constraint, a unique clustered index on the column or columns is automatically created if a clustered index on the table does not already exist and you do not specify a unique nonclustered index. The primary key column cannot allow NULL values.

When you create a UNIQUE constraint, a unique nonclustered index is created to enforce a UNIQUE constraint by default. You can specify a unique clustered index if a clustered index on the table does not already exist.

An index created as part of the constraint is automatically given the same name as the constraint name. For more information, see PRIMARY KEY Constraints and UNIQUE Constraints.

Index independent of a constraint

You can create a clustered index on a column other than primary key column if a nonclustered primary key constraint was specified.

Here is a picture of BOL for SQL Server 2008 R2 with the behaviour meant in comment evidenced in red

enter image description here

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.