0

I'm puzzled about how clustered primary keys work. I understand from the docs that rows are physically stored by primary key. Does this mean that inserting a new row with a key that fits in the middle would take ages because all the following rows would have to be shifted down? If not, how is this avoided?

k314159
  • 5,051
  • 10
  • 32
  • 1
    "rows are physically stored [ordered] by primary key" - wrong, they are logically ordered by primary key. Removing defragmentation gets the index in a position that logical and physical ordering is better correlated. See https://stackoverflow.com/questions/1251636/what-do-clustered-and-non-clustered-index-actually-mean/24470091#24470091 for more – Martin Smith Aug 25 '22 at 16:43
  • [This article](https://learn.microsoft.com/en-us/sql/relational-databases/sql-server-index-design-guide?view=sql-server-ver16#clustered-index-architecture) might help your understanding. Rows with contiguous keys (leaf nodes of the b-tree index) are stored in the same page and pages doubly linked in logical order. – Dan Guzman Aug 25 '22 at 16:48
  • It's called a B+ Tree, read up here for example https://learn.microsoft.com/en-us/sql/relational-databases/sql-server-index-design-guide?view=sql-server-ver16 – Charlieface Aug 25 '22 at 19:16

1 Answers1

0

These clustered indexes are organized into "pages". Pages are linked together in elaborate ways which we application programmers don't have to worry about. Pages often have free space in them. If a new "in the middle" row fits in the appropriate page, the server puts it there. If it doesn't the server performs a so-called "page split" to make room for the new entry. The pages that result from the split will then have more free space in them. Page splitting isn't a terribly expensive operation. But tons and tons of page splits fragment the clustered index and make a table slower to access.

New rows "at the end" generate new pages.

If you want to experience this for yourself, try making and populating table where a guid is the primary key. Pretty much every row you insert goes "in the middle" and you'll get lots of page splits.

Read this for details of index maintenance.

O. Jones
  • 103,626
  • 17
  • 118
  • 172