2

Where can I find a good representation of the of how data is stored in pages and how the B tree is constructed for a multi-column index (specifically for SQL server, but not necessarily)?

I'm referring to something like what you see in https://learn.microsoft.com/en-us/sql/relational-databases/reading-pages?view=sql-server-ver15 (for single column) but extended for multi-columns.

Another example for single column index: enter image description here

Thanks.

Ninjutshu
  • 53
  • 5
  • 1
    What do you mean more complete and why? That's *far* more complete than any description you'd find for other databases. Besides, either that page or another near it explain that column values in multicolumn indexes are combined to create one value – Panagiotis Kanavos Jul 21 '20 at 12:42
  • @PanagiotisKanavos: Thanks. I was not sure about how to extend this structure if we have more than one column. So I guess 'complete' don't say what I wanted to say. Edited accordingly. – Ninjutshu Jul 22 '20 at 00:32

2 Answers2

5

I found this example very informative, hope you are looking for something like this. It shows include columns as well (SQL-Server specific). If you don't need include-columns, simply take everything without 'age' and 'sex' in the leaf node. There is a good explanation in the original article (which I hope you might not need).

enter image description here

Reference - https://www.malinga.me/index-physical-structure-example-multi-column-non-clustered-index-with-includes/

Nashpaw
  • 110
  • 1
  • 7
  • Thanks a lot. This was what I was looking for. Was not sure if all the columns are indexed together or separate trees linked together. – Ninjutshu Jul 22 '20 at 00:35
  • 3
    Note that that's for a unique index on (First Name, Last Name). For a non-Unique index the clustered index key columns are added as index key columns, because there could be hundreds of pages full of different `('Kirstie', 'Southern')'s`. – David Browne - Microsoft Jul 22 '20 at 00:47
1

The index key values are sorted first by the first key column, then by the second key column, and then yt's exactly the same, except with additional columns on the non-leaf nodes. So if the first key column is a number, and the second the name of an animal, the non-leaf pages might have ranges like:

                                     (1,'cat')-(1000,'horse')
                                              ^
                  (1,'cat')-(500,'snake')               (500,'tiger')-(1000,'horse') 
                           ^                                         ^
(1,'cat')-(250,'elephant')   (250,'fox')-(500,'snake')          . . .
David Browne - Microsoft
  • 80,331
  • 6
  • 39
  • 67