Are page numbers of a book a good analogy for a clustered index?

Question

The title pretty much covers the question.

I think that the index of a book is a good analogy for a non-clustered index, as it demonstrates the extra storage and physical separation properties of a non-clustered index. I also think that the page numbers of a book represent well the physical ordering of data, similar to the structure of data with a clustered index.

However I'm a bit of a newbie to more advanced database theory. Does the analogy for page numbering make sense for a clustered index, or are there any properties of a clustered index where this analogy falls over?

Please note that the terminology of pages in the question refers to pages of a physical book, such as George Orwell's 1984, and not database pages.

I hope the question fits well here. If theoretical questions like this don't fit well, I'd be very grateful for being pointed in the right direction for where to ask these kinds of questions — Nick Bull, Jan 18 '21 at 15:27
Does this answer your question? Performance difference between Clustered and Non Clustered Index — John K. N., Jan 19 '21 at 15:06
@JohnK.N. No, that's to do with database pages, although I understand that both contain the term "pages", which may have led to the confusion. This question is specifically about the analogy of book pages - that is, physical book pages — Nick Bull, Jan 19 '21 at 15:19
Thanks for closing the question, I did suspect it didn't belong here. Could you recommend where to post such questions in the future? — Nick Bull, Feb 01 '21 at 11:25

score 3 · Accepted Answer · answered Jan 18 '21 at 15:56

3

Unfortunately I don't think there is a proper StackExchange for theoretical questions, but hopefully you gather good enough information here

Typically the "Phonebook" makes for a good analogy of how indexes work, not only because of the pages sorted by Names (i.e. the nodes of the B-Tree) but the sorting of the LastName, FirstName of the individual People within a specific page being representative of the leaves of the B-Tree. Brent Ozar has a good in-depth article on how indexing works that utilizes this analogy.

answered Jan 18 '21 at 15:56

J.D.

37,483
8
54
121

Thanks JD. Just to clarify a little more, do page numbers make a poor analogy, or an incorrect analogy? – Nick Bull Jan 18 '21 at 16:05
1

@NickBull I don't think there's anything wrong with using page numbers as part of the analogy but I think a phone book is a better analogy than a regular book because a regular book's data within a particular page is technically unordered, but a phone book's data is ordered even within the pages themselves (just like the leaves of a B-Tree). – J.D. Jan 18 '21 at 17:41
Dunno about others, but SQL Server is a hybrid as it has unordered rows within the pages, and a kind of lookup table contained in each page which is ordered, which refers to the rows in that page. – Charlieface Jan 19 '21 at 02:15
1

@Charlieface In the context of this question, pages are in regards to books not data stored on disk. We're only discussing the logical ordering of the data regarding indexes and B-Trees, so the even the leaf nodes (synonymous to a particular entry in a specific phone book page) is ordered theoretically. – J.D. Jan 19 '21 at 02:45
1

A phone book is a good enough analogy. Like any analogy it has its limits but it's a good place to start when trying to get a handle on index internals. – Michael Green Jan 21 '21 at 08:50

Are page numbers of a book a good analogy for a clustered index?

1 Answers1