How to Verify B+Tree Index Order in InnoDB Using bcview and Custom Tools

Goal

Demonstrate that within a secondary‑index leaf page of InnoDB the records are ordered first by the secondary key (column b) and, for equal b, by the primary key (column a).

Test Setup

Create a table with a primary key on a and a secondary index on b:

mysql> CREATE TABLE test (a INT, b INT, PRIMARY KEY (a), KEY (b));
mysql> INSERT INTO test VALUES (1,1);

Tools used: bcview – raw page viewer for .ibd files. mysqlblock – shows which InnoDB pages correspond to which index.

Both binaries are available at http://pan.baidu.com/s/1num76RJ.

Identify the Secondary‑Index Page

Run mysqlblock on the table file. Two data blocks are reported (pages 3 and 4). Page 3 is the clustered‑index root; page 4 is the root/leaf of the secondary index.

Match the INDEX HEADER (bytes 38‑74) of page 4 with INNODB_SYS_INDEXES to obtain the index ID:

SELECT * FROM information_schema.INNODB_SYS_INDEXES WHERE index_id IN (41,42);
+----------+------+---------+------+----------+---------+-------+-----------------+
| INDEX_ID | NAME | TABLE_ID| TYPE | N_FIELDS | PAGE_NO | SPACE | MERGE_THRESHOLD |
+----------+------+---------+------+----------+---------+-------+-----------------+
|       41 | PRIMARY |   40 | 3    | 1        | 3       | 24    | 50 |
|       42 | b       |   40 | 0    | 1        | 4       | 24    | 50 |
+----------+------+---------+------+----------+---------+-------+-----------------+

Thus page 4 (index ID 42) stores the secondary index on column b.

Inspect Raw Leaf Records

Use bcview to dump the leaf page (page 4). The first user record follows the infimum record; its offset can be calculated from the header (e.g., offset 99 + 27 = 126).

./bcview test.ibd 16 94 14 | more
current block:00000004--Offset:00094--cnt bytes:14--data is:010002001b696e66696d756d0002

The record layout on a leaf page is:

Cluster key fields (N bytes)

Transaction ID (6 bytes)

Roll pointer (7 bytes)

Non‑key fields (M bytes)

Insert Test Rows

Insert a set of rows with varying a and b values (all positive integers):

INSERT INTO test VALUES (5,1), (3,1), (4,2), (10,4), (7,4), (8,5), (11,5), (20,6), (21,6), (19,7), (16,7);

After each insertion, re‑run bcview to locate the new record’s offset and verify its position.

Utility to Print B:A Pairs

A small C program ( a.out) reads the leaf page, follows the linked list of records, and prints the b and a values in the order they appear on disk. Compile with:

gcc test.c -o a.out

Run:

./a.out test.ibd 4

Sample output:

Index_no is:42
find first one record!
B:1,A:1-->
B:1,A:3-->
B:1,A:5-->
B:2,A:4-->
B:4,A:7-->
B:4,A:10-->
B:5,A:8-->
B:5,A:11-->
B:6,A:20-->
B:6,A:21-->
B:7,A:16-->
B:7,A:19-->

The sequence shows that rows are sorted by b and, for identical b, by a, confirming the hypothesis.

Key Implementation Details

The program assumes a little‑endian Linux environment.

Signed integers are converted to the InnoDB internal representation by XOR‑ing with 0x80000000.

Only positive integer values are supported; zero or negative values are not handled.

The tool works on small tables where the secondary index fits in a single leaf page (no page splits).

Usage Summary

Determine the secondary‑index page number using bcview and mysqlblock (e.g., page 4).

Compile the C source and run ./a.out <ibd_file> <page_no>.

Observe the printed B:A sequence to verify ordering.

References for deeper InnoDB internals: original blog posts at http://blog.itpub.net/7728585/viewspace-2126470/ and related InnoDB system tables.