How Modern Indexing works in PostgreSQLPostgreSQL中现代索引的工作原理

 

Indexing is one of the most important parts of Database Management Systems索引是数据库管理系统最重要的部分之一

 

Indexing makes data retrieval fast; the DBMS does not need to scan every row of the table
Because of indexing, DBMs do not need to load the entire file in memory (without indexing, DBMSs have to load page by page of a table against which a query is made), which improves memory optimization索引使数据检索快速；DBMS无需扫描表中的每一行。由于索引，DBMS无需将整个文件加载到内存中（没有索引时，DBMS必须逐页加载查询所涉及的表），从而优化内存使用

 

What is Indexing and how does it works internally?什么是索引以及它内部如何工作？

 

Note: This article is written taking note of PostgreSQL注意：本文以PostgreSQL为例编写

 

Before moving into the internals of indexing, let’s see the types of indexing and how they are created在深入索引内部之前，让我们看看索引的类型以及如何创建它们

Types of indexing索引的类型

1. Clustered Indexing :聚簇索引：

2. Non-Clustered Indexing :非聚簇索引：

MySQL stores only non clustered index as a separate file on disk, but PostgreSQL treats every type of indexing as non-clustered and saves it as a separate file on diskMySQL仅将非聚簇索引作为单独文件存储在磁盘上，但PostgreSQL将所有类型的索引视为非聚簇索引，并作为单独文件保存在磁盘上

 

How indices are created by query如何通过查询创建索引

The following query creates an index on the Email column on the users table以下查询在users表的Email列上创建索引

 

CREATE INDEX idx_users_email
ON users(email);CREATE INDEX idx_users_email ON users(email);

 

Assuming the table is already containing thousands of records假设表中已包含数千条记录

 

idx_users_email will be the name of the index; it will be stored as metadata of that indexidx_users_email将是索引的名称；它将作为该索引的元数据存储

As you run the above query, Postgres starts scanning the table in our example. It starts scanning the Users table当你运行上述查询时，Postgres开始扫描我们的示例表。它开始扫描Users表

 

Before we go further lets understand how a table is stored on the disk在进一步之前，让我们了解表是如何存储在磁盘上的

 

DBMs stores the table as a file. Suppose the table contains 10k records, then that file is divided into pages, and each page is of 8 kbDBMS将表存储为一个文件。假设表包含10k条记录，那么该文件被划分为页面，每个页面大小为8 KB

Now back to the indexing process, which is in progress, while scanning the table dbms or in our case Postgre it scans according to key which is ‘Email’ column, it sorts alphabetically and starts storing in the indexing file (Note that Postgres by default sorts records according to key which is used to create an index), but it only stores certain info like primary key and most importantly the physical (not actual but logical address which may be used to calculate actual physical record address on the Disk) address of that record, so that Postgres can directly locate that record while fetching现在回到正在进行的索引过程，在扫描表时，DBMS或本例中的Postgres根据键（即'Email'列）进行扫描，按字母顺序排序并开始存储在索引文件中（注意，Postgres默认根据用于创建索引的键对记录进行排序），但它只存储某些信息，如主键，最重要的是该记录的物理地址（不是实际地址，而是逻辑地址，可用于计算磁盘上实际物理记录地址），以便Postgres在获取时可以直接定位该记录

Suppose for 10 k records, the indexing file stores 100 pages假设对于10k条记录，索引文件存储了100页

 

Organization of the Index File索引文件的组织

 

Each Index has root pages called page 0 每个索引都有根页，称为第0页

Each page has a max limit, which shows Postgre that what the upper limit so that it can determine the required value is on the same page or the next page每个页面都有一个上限，告诉Postgres上限值，以便确定所需值在同一页还是下一页

Example: Charlie is pointing to page 1
Michal is pointing to page 2 as M comes after C
Zoey is on the last page示例：Charlie指向第1页，Michal指向第2页，因为M在C之后，Zoey在最后一页

So if the query is finding value Daniel, then Postgres will start on page 0. If Daniel is smaller than Michel, it will be on page 2因此，如果查询要查找值Daniel，Postgres将从第0页开始。如果Daniel小于Michel，它将在第2页

In this way, the indexing file is organized索引文件就是这样组织的

 

Note: when you create an index on an existing table, it will take some time for sorting data and creating a new index file on disk注意：当你在现有表上创建索引时，排序数据和创建新索引文件到磁盘需要一些时间

 

Now we will see what will actually happen, like how the index file is loaded in memory and loaded in the B+ Tree, and how it finds the physical address and retrieves the record现在我们将看到实际发生的情况，比如索引文件如何加载到内存并加载到B+树中，以及如何找到物理地址并检索记录

For example, Postre receives a query to retrieve the record of a user whose email is ‘daniel@gmail.com’, as we have indexing for the email column. Postgres loads the first page of the index file, as each page is 8 KB, it is easy to calculate the first page and load in memory例如，Postgres收到查询以检索电子邮件为'daniel@gmail.com'的用户记录，因为我们有电子邮件列的索引。Postgres加载索引文件的第一页，由于每页为8 KB，很容易计算第一页并加载到内存中

 

Now Postgres loads page 0 in the memory buffer and starts the process as given below现在Postgres将第0页加载到内存缓冲区中，并开始如下过程

It looks for the page header, in that header, it finds the pd_special pointer, which shows PostgreSQL that index metadata is stored at the end
For extra verification, it checks flags BTP-ROOT AND BTP-META它查找页头，在页头中找到pd_special指针，该指针告诉PostgreSQL索引元数据存储在末尾。为了进一步验证，它检查标志BTP-ROOT和BTP-META

 

Next important thing this page will contain is line pointers, these are the physical addresses of each record against the key, they become useful when PostgreSQL finds right page for a given key该页面包含的下一个重要内容是行指针，这些是每个记录对应键的物理地址，当PostgreSQL找到给定键的正确页面时，它们变得有用

 

Index page contains ranges against uppar limits, means it notes down ranges according to available data, for example table contains records and in our example our key is Email field, now suppose there are 3k records whose emails starts with letter ‘a’ then pages of these records will be more, if there are only 1k records whose email is starting from letter ‘z’ then pages for these records will be less, so in this way page range is maintained.索引页面包含针对上限的范围，意味着它根据可用数据记录范围。例如，表包含记录，在我们的示例中键是Email字段。假设有3k条记录的电子邮件以字母'a'开头，那么这些记录的页面会更多；如果只有1k条记录的电子邮件以字母'z'开头，那么这些记录的页面会更少。这样维护页面范围

 

All ranges will be listed down, another example being if the table has  some records whose emails starts with ‘a’ but subsequent letters are missing, it means there are no records whose emails start with letter ‘b’ or ‘c’ instead there are records whose emails directly starting from letter ‘i’  then page 2 will contain records whose emails starts with letter ‘i’, 所有范围都将列出。另一个例子是，如果表中有一些记录的电子邮件以'a'开头，但后续字母缺失，意味着没有记录以'b'或'c'开头，而是有记录直接以'i'开头，那么第2页将包含以'i'开头的记录

All these range calculations are done while creating the index 所有这些范围计算都是在创建索引时完成的

So now we have ranges, and it is easy to find the appropriate page现在我们有了范围，很容易找到合适的页面

 

After finding the right page, that page is loaded into the B tree (Balanced Tree Structure), and that page is called the leaf page.
Leaf page and every other page will have a Tuple ID called as TID (Because any page can be a leaf page, it depends on which column you are using and which records are on which pages). By using this TID, Postgres will calculate the actual disk address of that record找到正确的页面后，该页面被加载到B树（平衡树结构）中，该页面称为叶页面。叶页面和其他每个页面都有一个元组ID，称为TID（因为任何页面都可以是叶页面，这取决于你使用的列以及哪些记录在哪些页面上）。通过使用这个TID，Postgres将计算该记录的实际磁盘地址

 

How does Postgres find right TID? In our case Tuple is it Daniel?Postgres如何找到正确的TID？在我们的例子中，元组是Daniel吗？

 

Postgres does binary search on all TIDs that are loaded in the leaf node, because the leaf node may contain thousands of tuples, and scanning top to bottom is time-consumingPostgres对加载到叶节点中的所有TID进行二分搜索，因为叶节点可能包含数千个元组，从上到下扫描很耗时

Once the physical address is found, postgress locate that record directly. Because PostgreSQL is written in C they may be using the function fseek()/iseek() or pread(), which can read a record based on physical address一旦找到物理地址，Postgres直接定位该记录。因为PostgreSQL是用C编写的，他们可能使用函数fseek()/iseek()或pread()，这些函数可以根据物理地址读取记录

 

OS System Calls level optimization in Modern Indexing现代索引中的操作系统系统调用级优化

 

Page 0 is always needed, so Postgres keeps page 0 in RAM always, because reading everytime from the disk is time is time-consuming第0页总是需要的，因此Postgres始终将第0页保留在RAM中，因为每次从磁盘读取都很耗时

Modern indexing uses a system call in Linux called io_uring which makes it possible to make synchronous call to disk, most of the system calls to disk were async this tradition was broken by advent of io_uring, developed by a Linux Kernel Engineer from Meta named Jens Asboe现代索引使用Linux中的一个系统调用io_uring，它使得对磁盘进行同步调用成为可能。大多数对磁盘的系统调用是异步的，这一传统被io_uring的出现打破，它由Meta的Linux内核工程师Jens Axboe开发

We will cover the exciting story of io_uring and its entire functionality in some other article我们将在另一篇文章中介绍io_uring的精彩故事及其全部功能

 

We cover deep topics like Garbage Collector Internals, Linux Kernel Internals, Hypervisor Internals, Distributed Computing, Open Source System Code Snippets explained, Custom Memory Management, Also we cover exciting Tech Stories, Underdog Companies stories, Extraordinary Developers stories.我们涵盖深度主题，如垃圾收集器内部、Linux内核内部、虚拟机监控器内部、分布式计算、开源系统代码片段解释、自定义内存管理，以及激动人心的技术故事、弱势公司故事、杰出开发者故事

Our Contents are useful for CS Students to CTO of any company. Consider subscribing to our newsletter and it’s free.我们的内容对从CS学生到任何公司的CTO都有用。考虑订阅我们的新闻通讯，而且是免费的

We publish 3 deeply researched articles 3 times a week我们每周发布3篇深度研究的文章，每周3次

 

Subscribe to our free Newsletter订阅我们的免费新闻通讯