MySQL innodb: if all the tuples are stored in the clustered Index then why do we call it index?
Let's approach it from two other perspectives...


The data needs to be stored somehow.  Perhaps unordered, perhaps based on a ROWNUM, or InnoDB's approach of ordering it according to the PRIMARY KEY.
In InnoDB the data structure and an INDEX structure are virtually identical -- both are BTrees of 16KB blocks with the 'items' ordered according to some KEY.  (I suggest that the documentation has confused you because it is hinting at the symmetry without enough background.)


Ordering the data according to one of the indexes (the PK) is actually a performance advantage for some queries.  In particular, if you want to look up a row by the PK, you can't get any faster.  If you want to scan a subset of the rows and do it in PK, order, you can do it any faster.

I assume you understand a BTree?  (See Wikipedia.)  InnoDB actually uses a B+Tree, very similar to a BTree, but adds links to make range scans more efficient.

Aside from nodes arranged in a tree, what is in the "leaf" nodes?

For the data / PRIMARY KEY, the leaf nodes contain all the columns of each row.  This is what is meant by "clustered".

For a secondary key (any index other than the PK), the leaf nodes contain a copy of the columns of the PK.  So, to look up a row via a secondary key, first you dig into its BTree to find the PK of the actual row, then you dig into the data to find the row.

One optimization is to use a "covering" index.  This is when all the columns needed anywhere in a SELECT are in a single index.  Guess what?  Now a Secondary index acts like a "table".  You don't need to bounce over to the data/PK BTree.

Each BTree for one table has its nodes stored in the .ibd file (assuming innodb_file_per_table=ON).  Each BTree is separate, aside from the PK linking.  (Think of ibdata1 and "tablespaces" are collections of tables thrown into a single disk file.)

You mentioned "pointer".  Mostly InnoDB gets away from pointers.  In the PK case, you arrive at the data; no need for a "pointer".  In the case of a secondary key, the copy of the PK serves as the "pointer".

As a Rule of Thumb, the nodes of either type of BTree have about 100 subnodes.  This implies that the BTree for a million-row table or index is about 3 levels deep.  (Think "log-base-100".)

Since fetching blocks is far more costly than rummaging through a block, counting disk hits is the main performance metric in an I/O-bound InnoDB table.

(MyISAM is radically different.)

(From comments:)

An InnoDB with just a PRIMARY KEY contains a single BTree.  The data is sorted according to the PK.  Lookups by PK are optimal.  That is, 'entire table and its data is in the cluster index structure'.

Inserting into such a table has multiple situations:

If you are 'randomly' inserting into the table, then the operation is technically Order(log n), such as 3 for a million-row table.  For all practical purposes, you can pretty much ignore drilling down the BTree.

A typical case is having id INT AUTO_INCREMENT PRIMARY KEY.  In this case, inserts are (normally) at the 'end' of the table.  (I do not happen to know if there is any optimization to avoid the repeated drill-down, but since this is a very common situation, I expect the developers have done a good job.)

Is an insert-heavy table inefficient?  Not really.  INSERTs have to go somewhere.  Granted, the typical table is read more than it is written, but still, "don't worry".

If you are doing thousands of INSERTs per second, there are various techniques to speed things up.  However, they focus on transactions, parsing, scattering, etc, not on the structure of the PRIMARY KEY.  One notable exception:  if the PK is a UUID, and the table is huge, you will be I/O-bound and probably have big problems.