An old article came out

The storage structure of a table

A table has only one partition by default (SQL Server’s partitioned table technology allows the table to be split horizontally, resulting in multiple partitions). Inside the partition is stored data, which can be stored in two forms: heap or B+ tree, the structure of which is described below. ,

page

A page is the smallest unit of data storage. The page types are data page, index page, Log_mixed_page, Lob_tree_page, and IAM page

A data page can store 8K (8192 bytes, minus the 96-byte header) of data. Data page inside is the data row, the data row cannot cross the page.

Question: that line of data can exceed 8K, more than 8K not cross-page?

SQL Server 2000 has this limitation. SQL Server 2005 broke the limit of 8K per row, but the size of SQL Server columns cannot exceed 8K (for example, you cannot define vARCHAR (9000) or nvARCHAR (5000)).

If a row of data exceeds 8K, the fields exceeding 8K are stored on the overflow page, with a pointer on the original row pointing to the overflow page.

Some people might say varchar(Max), nvarchar(Max), text, image, but this type is not LOB.

LOB(Large Object) is a data type used to store large objects, each LOB can be 2GB. LOB columns can span multiple pages, and pages are not necessarily contiguous.

Zone (also called extension zone)

Extents (also called extents) are collections of pages. An extents contain 8 pages and are 64K in size. Note: extents are not table partitions. There is only one table partition per table by default.

Heap structure

A heap is a table without a clustered index. The data in the table is not sorted by any field. Link the pages of the heap together using the “Index Allocation Mapping (IAM)” page. As shown below:

The data pages and rows in the heap are not in any particular order; Pages are not linked together. The only logical connection between data pages is the information recorded in the IAM page. There is no close connection between pages. Use IAM pages to find each page in the collection of data pages. In terms of data storage management, it is difficult to use heap to manage a large table, and the tables that are often used have clustered indexes.

A table scan or serial read operation can be performed on the heap by scanning IAM pages to find an extended extent that houses the pages of the heap. Because IAM represents the extentsin the order in which they exist within the data file, this means that serial heap scans are performed sequentially along each file. Using the IAM page to set the scan order also means that rows in the heap are generally not returned in the order they were inserted.

The index

The index storage structure of MSSQL is B+ tree, which is a balanced multi-fork tree.

B tree and B+ tree

Why are B+ trees better for indexing?

1. Because the page size is fixed, the B+ tree can hold more index values, so the index depth is relatively shallow, and the search performance is better.

2, b+ leaf level nodes, a bidirectional linked list, range lookup is very fast.

B+ tree structure:

When a clustered index is added to a table, its structure becomes a B+ tree, and data records become part of the B+ tree. The physical order of the data is in the order of the index fields, and since there must be only one physical order, only one clustered index can be added to the table.

Clustered index

The following diagram shows the storage structure of a single field clustered index (assuming the clustered index is added to Name)

  1. Clustered indexes are stored in a B-tree structure. The root and middle nodes are index pages, and the leaf nodes are data pages.
  2. When a table has a clustered index, the data is stored not in a heap, but in a B-tree structure, where the data is recorded as part of the B-tree, the leaves of the B-tree.
  3. The index page contains the index row, which is composed of the index key value and the pointer, which points to the page ID of the next level index. If the next level is a data page, it points to the data page ID (not the data row ID).
    1. The data page contains the data row. If the size of the data row exceeds 8060 bytes, the excess part will be saved to the overflow page, and the data row will have a pointer to the overflow page.
    2. The above diagram has a defect (the association between pages is not indicated), index pages of the same level are related to each other, a two-way linked list, each index page has a pointer to the next page.
    3. The data page is also a bidirectional linked list, pointing to the previous and next pages. The data may not be physically continuous, but it must be logically continuous. So range queries are fast.
  4. The data is ordered, in the order of clustered index fields, so a table can have only one clustered index. As shown in the figure above, the data records on the far right are clearly arranged in ascending order of Name.
  5. B+ tree lookup: As shown in the figure above, suppose you want to find a record with Name=Greene
Start with the root node: >= 'Bennet' and < 'Karsen' data --> enter index page 1007 (Greene's record should be on this page again) >= 'Karsen' and < 'Smith' data --> enter index page 1009 >= 'Smith' and < Data for XXXXXXX --> go to index page 1062 and search from middle node index page 1007: >= 'Bennet' and < 'Greane' data --> go to data page 1132 >= 'Greane' and < 'Hunter' data --> go to data page 1133 (Greene's record should look up this page again) >= 'Hunter' and < XXXXXXXX data --> Go to data page 1127 and finally get the row Name=Greene from data page 1133Copy the code

How is the index key of the root node determined?

1. How is the storage index key in the root node determined? Why Zhangsan and not Lisi or something?

  1. Take the first index key of each data page and form the index page upward.
  2. Then use the first of each of the lowest index pages to form the index page, and so on, up to the root node. This gives the root node’s index key

PS: that is, the first record must be in the root node, as the following DBCC analysis confirms.

How is the index level determined?

If there are 100 million rows in a table, and those 100 million rows make up 10 million pages,

The clustered index field is an Int (Int is 4 bytes), and an index page can only store 8K (8060 bytes) of data:

  1. Then the data page upper layer needs 40 million bytes /8060 bytes =4963 index pages. (Because the index point is the ID of the index page, the index at the top of the data page only needs 40 MB)
  2. The next level up (4963*4)/8060 = 3 index pages
  3. One more index page, and now you have the root node.

The number of levels (or index depth) of an index is determined by the size and number of index keys.

Structure of composite clustered indexes

There will be multiple key values in the index row, as shown in the figure below. The following figure is taken from the DBCC analysis

Nonclustered index

The difference between a non-clustered index and a clustered index is that the leaf level is no longer a data page, that is, the data is no longer part of the index structure.

What is stored at the leaf level of a non-clustered index? We can discuss two cases: non-clustered indexes on a heap table and non-clustered indexes on a clustered table (that is, a table with clustered indexes) have different leaf level contents.

A non-clustered index on the heap

A non-clustered index on a B+ tree

Note that if the table does not have a clustered index and creates a non-clustered index, the non-clustered index uses the row number. If you add a clustered index to the table, the RIDs referenced by all non-clustered indexes will be changed to clustered keys. This can be very costly to performance, so it is best to build clustered indexes first and then non-clustered indexes.

1. For non-clustered indexes on the clustered table, why does the leaf level node use the key value of the clustered index instead of the RID to locate records?

If you use RID localization, if a page split occurs on a data page, then the newly split half-page data, the RID of the original half-page data row in the index, will be updated to the new RID.

This process is very inefficient, because the half-page data row non-clustered index, generally not together, are scattered in the index page, lookup efficiency is very low. In the case of clustered index keys, even if the clustered index has a data page split, it has no effect on the non-clustered index.

The advantages and disadvantages

  1. Disadvantages: The search efficiency is relatively low, because after the search of the non-clustered index, the search must be based on the clustered index.
  2. Advantages: The real data location is using clustered index keys, not RIDs. This does not affect the non-clustered index when a data page split occurs.

FAQ Analysis

Why does using indexed field queries provide efficiency?

Instead of table scanning, index lookups are used, geometrically increasing efficiency

Do indexes make it less efficient to add, delete, and modify? How is it affected?

new

  • The efficiency of the new operation is really reduced because there is actually one more step to update the index. The efficiency impact of the new operation is more related to the page splitting operation.
  • For clustered indexes: if the clustered index keys are not progressively incremented, data may be inserted in the middle of the data page, which may result in split data pages (and may cascade up to split index pages at all levels). Page splitting can result in internal fragmentation and external fragmentation. If there is too much external fragmentation, range lookup can result in sequential IO becoming random IO(the disk cantilevers back and forth to read data), which is very inefficient.
  • Page splitting and cascading upward are indeed inefficient, so it is necessary to cluster index fields in an orderly fashion.
  • For non-clustered indexes: as long as the clustered index is ordered, data page splitting is less. However, the added data can still lead to index page fragmentation, which is inevitable because it is impossible to design non-clustered index key values to trend upward.
  • Page split see below, write later

Modify the

Index updates only occur if the value of the index field is changed. If the index field is not modified, I understand that efficiency should not be reduced

delete

Data is deleted and indexes need to be updated, reducing efficiency.

PS: Although updating an index has some impact on the efficiency of modify and DELETE operations, it is necessary to find a row to UPDATE or DELETE a row, so indexes can actually be helpful for UPDATE or DELETE operations with complex WHERE conditions. The effectiveness of locating a row using an index usually makes up for the extra overhead of updating the index, unless the index is poorly designed.

Why do index queries have left-most rules

The index lookup matches from the leftmost field. If a composite index is queried using only the middle and trailing fields, the index cannot be used

Performance differences between clustered and non-clustered indexes

  • Non-clustered indexes are less efficient than clustered indexes. Because clustered indexes are physically ordered and coherent, range lookups are fast once the starting point of the data is found.
  • Data in a non-clustered index is disordered and incoherent. Range lookups can only be retrieved one index at a time. But it is still much more efficient than a full table scan without an index.