Embedded Pointers and its implications

While reading for a MCQ based test, I came across this fascinating concept of Embedded Pointers which I wanted to explore in this article.

Having pretended to know DS and Algorithms for the last 10 years, I would rather be too proud to admit that I know what Embedded pointers are. While talking about embedded pointers, we dont *really* consider conceptual view of a database. Rather, an embedded pointers are an explicit physical storage addresses, page offsets, or record IDs stored directly within a data record’s structure.

Context of an embedded pointer -

• In relational storage world, establishing a relationship (like Department-Employee) relies on foreign keys and secondary indexes.
• But, in terms of Low-Level Organization of data, we have this common data structure for efficient retrieval (using indexing techniques).
• In engines like InnoDB (MySQL), leaf nodes use embedded pointers(e.g., next_page and prev_page offsets) to form a doubly linked list across disk pages. This enables efficient sequential range scans without re-traversing the root B+ tree.
• In graph database world, you can think of an index-free adjacency approach to model data. Here, nodes contain direct embedded pointers to adjacent edges and neighbor nodes, allowing $O(1)$ traversal steps.

In InnoDB storage, let me illustrate with an actual example. Without going into too much detail, tables are organized as clustered indexes structured as B+ trees. The primary key of a table forms the B+ tree, and the leaf nodes store the complete table rows (data payloads).
For example,
CREATE TABLE Employees ( emp_id INT PRIMARY KEY, name VARCHAR(50), salary INT ) ENGINE=InnoDB;

Know that in InnoDB, all data is divided into fixed-size 16 KB pages. Each page has a unique 4-byte Page Number (like Page 3, Page 10, Page 11). In this case, we will consider a type of Embedded pointer called Page Link Pointers: Leaf nodes store embedded FIL_PAGE_NEXT and FIL_PAGE_PREV page numbers in their headers to form a doubly linked list across disk pages.

Horizontal pointers

Implementation details -

Get Karthick Kannan’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Every InnoDB page starts with a 38-byte Page Header (FIL Header). Within this header, InnoDB embeds two 4-byte page number pointers:

• FIL_PAGE_NEXT (Offset 12): Page number of the next logical leaf page.
• FIL_PAGE_PREV (Offset 8): Page number of the previous logical leaf page.

In above example:

• On Page 10: FIL_PAGE_NEXT stores 11.
• On Page 11: FIL_PAGE_PREV stores 10.

Why this matters?

If we ever run a query like this -SELECT * FROM Employees WHERE emp_id >= 101 AND emp_id <= 208;

1. InnoDB navigates down the tree from Root to Leaf (Page 10) via B+ tree vertical traversal first
2. It reads records on Page 10 (101: Alice, 105: Bob).
3. To find the next record, InnoDB does not re-traverse the root tree. It reads the embedded pointer FIL_PAGE_NEXT = 11 directly from Page 10's header and immediately jumps to Page 11 to read 201: Charlie and 208: David.

Putting it all together, lets look at a toy-example of B+ Tree in Python

class BPlusTreeNode:
    def __init__(self, is_leaf=False):
        self.is_leaf = is_leaf
        self.keys = []
        # For Internal Nodes: pointers to child BPlusTreeNode instances
        # For Leaf Nodes: key-value data payloads or record slots
        self.children = []


class BPlusTreeLeafNode(BPlusTreeNode):
    def __init__(self):
        super().__init__(is_leaf=True)
        # Embedded pointers for horizontal scans (doubly linked list across leaves)
        self.next = None
        self.prev = None