How PageIndex Builds a Tree Structure for Nested Sections and Subsections

PageIndex converts flat table-of-contents entries into a hierarchical tree by parsing dotted structure codes (like 1.2.3) to identify parent-child relationships, then recursively nesting nodes via the list_to_tree function in pageindex/utils.py.

The VectifyAI/PageIndex repository provides intelligent document indexing that preserves hierarchical relationships. Unlike flat indexing systems, the tree structure in PageIndex explicitly models nested sections and subsections, enabling precise semantic retrieval across complex documents with deep heading hierarchies.

The Three-Phase Pipeline for Hierarchical Tree Construction

PageIndex builds its tree through a strict three-phase pipeline that transforms raw document content into a clean, nested JSON structure.

Phase 1: TOC Generation with Structure Codes

The pipeline begins in pageindex/page_index.py with the generate_toc_init and generate_toc_continue functions. These LLM-powered extractors scan the document and produce a flat list where every heading is annotated with a structure code—a dotted numeric identifier such as 1, 1.1, 1.2, or 2.1.3.

Each entry also includes an optional <physical_index_X> tag that marks the specific page where the heading starts. This flat list represents the document's hierarchy in a linear format, ready for transformation.

Phase 2: Normalisation and Page Range Enrichment

Before tree assembly, the raw TOC data undergoes cleaning in pageindex/utils.py via the post_processing function. This phase removes temporary fields, converts <physical_index_X> strings to integers, and enriches each item with start_index and end_index page numbers.

This normalization ensures that every node in the eventual tree knows exactly which pages it spans, enabling precise content retrieval later in the pipeline.

Phase 3: Tree Assembly from Flat List to Nested Structure

The final phase occurs in pageindex/utils.py (lines 50-96) within the list_to_tree function. This helper walks the normalized flat list once, creates a node for every entry, and attaches each node to its parent by examining the structure code.

The parent code is derived by splitting the structure string on dots and dropping the last segment—"1.2" becomes parent "1", and "2.1.3" becomes parent "2.1". Nodes without a parent (top-level sections) become root nodes. After building the hierarchy, the clean_node function recursively removes empty nodes arrays from leaf nodes, yielding a clean nested JSON-like tree.

How list_to_tree Constructs the Hierarchy

The list_to_tree function implements a deterministic algorithm for parent-child resolution that handles arbitrarily deep nesting.

Parent Code Detection

At the core of the algorithm is the get_parent_structure helper function (lines 50-57 in utils.py):

def get_parent_structure(structure):
    if not structure:
        return None
    parts = str(structure).split('.')
    return '.'.join(parts[:-1]) if len(parts) > 1 else None

This function splits the dotted structure code (e.g., "2.2.1") into segments, removes the last segment, and rejoins the remainder to identify the parent code ("2.2"). When the structure contains no dots, the function returns None, signaling a root-level section.

Node Creation and Linking

For each item in the flat list, list_to_tree creates a node dictionary containing title, start_index, end_index, and an empty nodes list. It stores these nodes in a lookup table keyed by their structure code.

The function then iterates through the lookup table, retrieves each node's parent code, and either appends the node to its parent's nodes array or adds it to the root list if no parent exists. This single-pass approach ensures O(n) complexity regardless of nesting depth.

Cleaning Empty Arrays

After the initial assembly, the clean_node function (lines 86-95) recursively traverses the tree and removes the nodes key from any leaf nodes where the array is empty. This produces a compact output where only nodes with actual children contain a nodes field.

Working with the PageIndex Tree Structure

The following examples demonstrate how to generate and manipulate the hierarchical tree in practice.

Generate a Tree from a PDF

The primary entry point is the page_index function in pageindex/page_index.py (lines 470-476), which orchestrates the entire pipeline:

from pageindex.page_index import page_index

# Process a PDF into a hierarchical tree

tree = page_index(
    doc="path/to/document.pdf",
    model="gpt-4o-2024-11-20",
    toc_check_page_num=20,
    max_page_num_each_node=10,
    max_token_num_each_node=20000,
    if_add_node_id="yes",
    if_add_node_summary="yes",
    if_add_doc_description="yes",
)

print(tree)

This call triggers TOC detection, structure generation, and list_to_tree conversion, returning the final nested structure.

Manual Tree Construction from Flat Data

To inspect the transformation process, you can manually invoke list_to_tree with a flat list of sections:

from pageindex.utils import list_to_tree

flat_sections = [
    {"structure": "1", "title": "Introduction", "start_index": 1, "end_index": 3},
    {"structure": "1.1", "title": "Background", "start_index": 1, "end_index": 2},
    {"structure": "1.2", "title": "Objectives", "start_index": 2, "end_index": 3},
    {"structure": "2", "title": "Methodology", "start_index": 4, "end_index": 10},
]

hierarchy = list_to_tree(flat_sections)

Traverse and Display the Hierarchy

Once you have the tree, you can walk it recursively to display the nested structure:

def walk_tree(node, depth=0):
    indent = "  " * depth
    print(f"{indent}{node['title']} (pages {node['start_index']}-{node['end_index']})")
    
    for child in node.get('nodes', []):
        walk_tree(child, depth + 1)

# Display all root sections

for root_node in hierarchy:
    walk_tree(root_node)

This produces readable output showing the parent-child relationships and page ranges for each nested subsection.

Key Source Files and Functions

The hierarchical tree construction is implemented across two primary modules:

File	Key Functions	Responsibility
pageindex/page_index.py	generate_toc_init, generate_toc_continue, page_index	Orchestrates the workflow: extracts raw headings with structure codes via LLM prompts, validates page numbers, and invokes the tree-building pipeline (lines 470-476).
pageindex/utils.py	post_processing, list_to_tree, get_parent_structure, clean_node	Contains the core tree-building logic (lines 50-96), including parent code detection, node linking, and empty array cleanup.

These files work together to transform flat document outlines into the nested tree structure that PageIndex uses for semantic indexing.

Summary

• PageIndex constructs hierarchical trees using dotted structure codes (e.g., 2.1.3) extracted by LLM-powered TOC generators in pageindex/page_index.py.
• The list_to_tree function in pageindex/utils.py (lines 50-96) performs O(n) assembly by parsing parent codes—splitting on dots and dropping the last segment—to link children to parents.
• The algorithm handles arbitrarily deep nesting through recursive cleaning (clean_node) that removes empty child arrays from leaf nodes.
• Each tree node carries page range metadata (start_index, end_index) enabling precise content retrieval for specific sections and subsections.

Frequently Asked Questions

How does PageIndex determine the parent of a nested subsection?

PageIndex uses the get_parent_structure function in pageindex/utils.py to derive parent relationships. This helper splits the dotted structure code (e.g., "3.2.1") on periods, removes the final segment, and rejoins the remainder to identify the parent code ("3.2"). If no dots exist in the code, the function returns None, indicating a root-level section.

What is the maximum depth of nesting supported by the PageIndex tree structure?

The tree structure supports arbitrarily deep nesting limited only by the document's actual hierarchy and Python's recursion depth. The list_to_tree function processes all nodes in a single pass regardless of depth, and the clean_node function uses recursion to traverse and clean the entire hierarchy. Structure codes with multiple dots (e.g., "4.1.2.3.5") are parsed correctly at any depth.

How does the tree structure handle page ranges for parent sections?

During the normalisation phase in pageindex/utils.py, the post_processing function enriches each node with start_index and end_index values representing the first and last page of that section. Parent sections automatically span from the start of their first child to the end of their last child, ensuring that intermediate nodes in the tree carry accurate page metadata for retrieval operations.

Can I manually construct a tree from a custom list of sections without using the LLM extraction?

Yes. The list_to_tree function in pageindex/utils.py is exposed as a public utility and accepts any list of dictionaries containing structure, title, start_index, and end_index keys. You can manually define your hierarchy using dotted structure codes (e.g., "1", "1.1", "1.1.1") and pass the list directly to list_to_tree to generate the nested JSON structure without invoking the LLM-based TOC extraction.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}