CODEWITHSUNDEEP
mysqlinnodb
Jack Ma
Jack Ma

Reputation: 307

Real relation between InnoDB secondary index and primary index

For table t:

mysql> show create table t\G
*************************** 1. row ***************************
       Table: t
Create Table: CREATE TABLE `t` (
  `a` int(11) NOT NULL,
  `b` int(11) DEFAULT NULL,
  `c` int(11) DEFAULT NULL,
  PRIMARY KEY (`a`),
  KEY `b` (`b`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> select * from t;
+---+------+------+
| a | b    | c    |
+---+------+------+
| 1 |    3 |    3 |
| 2 |    2 |    4 |
| 3 |    3 |    4 |
| 4 |    5 |    2 |
+---+------+------+

there are some rows with the same column b value, for select * from t where b = 3, how innodb found all primary keys for secondary index of b = 3? And how the leaf node of secondary index of b look like?

Upvotes: 2

Views: 209

Answers (1)

Bill Karwin
Bill Karwin

Reputation: 562438

The short answer is that the B-tree for a secondary index is organized by both the indexed column and the primary key. It's as if every secondary index has the id column appended to it.

For example:

id x y
1 12 'a'
2 12 'b'
3 24 'c'
4 12 'd'

Suppose id is the primary key and x is indexed as a secondary key. The real secondary key is (x, id).

The leaf nodes will therefore be:

(12, 1)
(12, 2)
(12, 4)

In this way the leaf nodes always include the primary key value as well.

Looking up a row by its secondary index therefore requires two searches in B-trees. The first to search the secondary index B-tree, which yields one or more leaf nodes with distinct primary key values. Then the primary key values are used to search the primary key B-tree (the clustered index), which yields exactly one leaf node for each primary key value, and in that node is found all the columns, including both indexed and non-indexed columns.

If you're interested in a great deal more detail, I recommend Jeremy Cole's series of blog posts: https://blog.jcole.us/innodb/

Upvotes: 3

Related Questions