![]() Non-leaf nodes (located at all levels except the bottom) contain records that consist of the smallest key (in Figure 2, the lowest alphanumeric value) in a block located at the next level and a pointer to this block.Īny search for a key K starts from the root node of the B-tree. The leaf nodes (shown in the bottom row in Figure 2) contain index records exactly like those in Figure 1 these records contain an index key and a pointer to a table row. Records in all blocks are ordered, and at least half of the block capacity is used in every block. The tree consists of hierarchically organized nodes that are associated with blocks stored on a disk. ![]() The basic structure of a B-tree is shown in Figure 2, using airport codes as the index keys. (Note that later you will see a bitmap index show up in the query plan, but it is different than a typical index). There are other types of indexes you can add to tables, but the B-Tree is the most common and what I will focus on for this article. PostgreSQL supports a lot of types of indexes.įor this article, I am going to only discuss B-Tree indexes because they are the most common index structure you will typically use. That is, a key may be logically associated with a list of pointers to rows rather than a single pointer.įigure 1 illustrates how to reach the corresponding table row when an index record is located however, it does not explain why an index row can be found much faster than a table row. If this column is indexed, the index must contain pointers to all rows containing this value of an index key. However, some columns, like the column city in the airport table, can have the same value in multiple rows. The example in Figure 1 has airport code as its value hence, this index supports search by airport code.įor this particular index, all values in the airport_code column are unique, so each index entry point to exactly one row in the table. The value of an index key usually is equal to the value of a table attribute. ![]() Each row of the index consists of an index key and a pointer to a table row. The right part of Figure 1 shows a table, and the left represents an index that can be viewed as a special kind of a table. Such filtering conditions specify certain restrictions on table attributes.įigure 1 shows how an index can speed up the access to the specific table rows. Although index structures can differ significantly among index types, the speed-up is achieved due to a fast check of some filtering conditions specified in a query. That is, any query produces the same results with or without an index.įinally, an index is created with the hope (or confidence) that it improves performance of a specific query or (even better!) several queries. Invisibility means that a user cannot detect if an index is present or absent when writing a query other than the time the query takes to process. Full instructions are in the appendix of this article to create the database you will need if you wish to follow along with the examples.) Redundancy means that an index can be dropped without any data loss and can be reconstructed from data stored in tables (the postgres_air database dump we will use with the examples comes without indexes, but you can build them after you restore the database. Let’s discuss each of the bullet points in more detail. Designed to speed up data selection based on certain criteria.A data structure is called an index if it is: Instead, we define an index based on its usage. Since there are many different index types in PostgreSQL (and new index types are constantly created) we won’t focus on structural properties to produce an index definition. Having this in mind, let’s start with defining what is an index. However, a surprising number of people, including database developers and report writers and, in some cases, even DBAs, use indexes, even create indexes, with only a vague understanding of what indexes are and how they are structured. What is an index? One might assume that any person who works with databases knows what an index is. It might seem to be a better idea to talk about indexes before we discussed execution plans, but query plans are a good place to start the performance journey and work our way in! This blog is going to be about indexes, why we need them, how they can help, and how they can make things worse. Specifically, we observed that in some cases PostgreSQL used sequential scan, and in some cases index-based access. We learned that an execution plan provides information about access methods, which PostgreSQL use to select records from a database. ![]() In the previous blog in this series, we learned how to produce, read and interpret execution plans.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |