Linear Trees in InnoDB


In InnoDB, a linear tree is a type of data structure used for indexing and searching data. Linear trees are also known as B+ trees. The key characteristic of a linear tree is that all the data is stored in a sorted order, with a pointer to the next leaf node. This allows for efficient searching and insertion of data.

InnoDB uses a modified version of linear tree called a “compressed” B+ tree. Each node of the tree contains multiple keys, and the keys are stored in a sorted order. The keys are used to determine the path that a query should take when searching for data. When a node is full, it is split into two nodes, with the middle key moving up to the parent node. This helps to keep the tree balanced and ensures that the search time is always logarithmic.

InnoDB uses linear trees to store the primary key and secondary indexes of a table. Each leaf node of the tree contains the actual data rows of the table. When a query is executed, the optimizer uses the keys stored in the tree to determine the most efficient path to the data. This allows InnoDB to quickly locate and retrieve the requested data.

Linear trees are commonly used in relational databases and other systems that need to store and retrieve large amounts of data efficiently. The use of linear tree in InnoDB provides many benefits, such as fast search and insertion, support for concurrent operations, and the ability to handle large amounts of data.

Python code to monitor unused and redundant indexes in InnoDB

In MySQL, you can use the MySQL Performance Schema to monitor the usage of indexes and detect unused or redundant indexes. The Performance Schema provides several tables that allow you to track the usage of indexes, including the table performance_schema.table_io_waits_summary_by_index_usage

import mysql.connector
# Connect to the MySQL server
cnx = mysql.connector.connect(user='<username>’,
# Create a cursor object
cursor = cnx.cursor()
# Execute a query to retrieve information about index usage
SELECT object_schema, object_name, index_name, SUM(count_fetch) as fetch_count, SUM(count_scan) as scan_count
FROM performance_schema.table_io_waits_summary_by_index_usage
WHERE object_schema NOT IN (‘performance_schema’, ‘sys’)
GROUP BY object_schema, object_name, index_name
ORDER BY fetch_count, scan_count;
# Fetch the results
results = cursor.fetchall()
# Print the index usage information
for row in results:
print(“Schema: “, row[0])
print(“Table: “, row[1])
print(“Index: “, row[2])
print(“Fetch Count: “, row[3])
print(“Scan Count: “, row[4])
# Close the cursor and the connection

This code creates a connection to the MySQL server using the mysql-connector-python library, creates a cursor object, and then executes a query to retrieve information about index usage from the performance_schema.table_io_waits_summary_by_index_usage table. The query groups the results by the schema, table, and index name and calculates the total number of fetches and scans for each index. The results are then fetched and printed.

You can use the results of this query to determine which indexes are not being used and may be redundant. For example, if an index has a low fetch count and a low scan count, it may not be needed and can be removed.

It’s worth noting that this is an example of how you can monitor index usage, and you should adjust the query to match your specific requirements. Also, it’s important to test any changes to indexes in a development environment before applying them to a production environment.


Linear trees, specifically the compressed B+ trees used in InnoDB, play a pivotal role in optimizing data storage, indexing, and retrieval in MySQL. These structures ensure efficient search and insertion operations, balancing the tree dynamically to maintain performance. Monitoring and managing index usage is crucial for maintaining database performance, and MySQL’s Performance Schema offers tools to identify and remove unused or redundant indexes effectively.

About Shiv Iyer 452 Articles
Open Source Database Systems Engineer with a deep understanding of Optimizer Internals, Performance Engineering, Scalability and Data SRE. Shiv currently is the Founder, Investor, Board Member and CEO of multiple Database Systems Infrastructure Operations companies in the Transaction Processing Computing and ColumnStores ecosystem. He is also a frequent speaker in open source software conferences globally.