Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I was reading the article on indexes at simple-talk, where it is written that

If a heap has a non-clustered index on it (as the primary key), and data is inserted into the table, two writes have to occur. One write for inserting the row, and one write for updating the non-clustered index. On the other hand, if a table has a clustered index as the primary key, inserts take only one write, not two writes. This is because a clustered index, and its data, are one in the same. Because of this, it is faster to insert rows into a table with a clustered index as the primary key than it is to insert the same data into a heap that has a non-clustered index as its primary key. This is true whether or not the primary key is monotonically increasing or not.

Isn't it wrong? Clustered indexed naturally resort to B+ trees, where only the keys are stored in intermediate nodes (unlike B-trees, where the entire record is stored. That is why B+ trees can fit more keys in a single page, resulting it being bulky in width but shorter in height), so all records are stored in the leaf pages (the pages themselves being logically sorted through linked-lists, while the data in each page being physically sorted). So if a record has to be updated, say the value 1 has to be updated to 7, won't the update need to be applied to both the key in the clustered index top node (this may, in cases, cause a re-structuring of the entire structure) and the corresponding value in the record in the leaf-page?

enter image description here Update: Okay, I did some study, and found that apart from the initial tree structure (where some values must be present twice, for example the key values in the node), when new values are inserted, they just fit into the leaf page, whereas the tree gets restructured to accommodate that. However, when, say 5 values are inserted, the 3rd value may cause the first inserted value (which is currently occupying only leaf level space) to cascade up, thus causing it to be written twice (once in the leaf level, other in the index level). Of course, such re-writes (although they don't occur at the time of insertion, they can occur later) will be much less compared to the two-time write which occurs each time there is an insertion into a heap with NCI, but still isn't it wrong to say that there is no re-write?

share|improve this question
2  
The paragraph you cite from the article, talks about Inserts. Your example talks about Updates. –  ypercube Sep 13 '12 at 14:45
    
Yeah, for indexes too. The row will get inserted into the correct position on the leaf level, but the new key value has to be put into the tree structure, right? For example look at the examples of inserting keys into a B+ tree at mec.ac.in/resources/notes/notes/ds/bplus.htm, each time the tree gets restructured. –  Cupidvogel Sep 13 '12 at 14:53
2  
I guess the author intended to say that inserting into a table with a clustered index and no other ones means you need to modify only one object. On the other hand, inserting into a table with one non-clustered index means you need to modify two objects. –  AlexKuznetsov Sep 13 '12 at 15:34
1  
You are partially right. When the clustered key is not monotonically increasing, you may have sometimes 2 writes. That's one reason why increasing keys (like IDENTITY or timestamp) are good choices for the CI. –  ypercube Sep 13 '12 at 15:36
4  
Index pages above the leaf contain only a pointer to each down-level page and the minimum key value that might be present on each page. Non-leaf pages do not include all keys below. –  Paul White Sep 14 '12 at 11:19

1 Answer 1

up vote 5 down vote accepted

I think the problem here is a difference in terminology.

The "number of writes" that's usually referred to is the number of object accesses, rather than the number of pages that get touched by the physical operation.

The reason why that's usually used as a metric in discussion is because it's a more "stable" and meaningful number to talk about. As we're getting into here, the number of pages touched by an INSERT statement for even a single row depends on many factors, so it's not a very useful quantity outside your own environment and situation.


The one thing I would pick at from the article quote is this (emphasis mine):

One write for inserting the row, and one write for updating the non-clustered index.

This may be confusing. Inserting a row into the base table would involve an insert to the base table, and also an insert into each nonclustered index (ignoring special index features), not an update.

So if a record has to be updated, say the value 1 has to be updated to 7, won't the update need to be applied to both the key in the clustered index top node (this may, in cases, cause a re-structuring of the entire structure) and the corresponding value in the record in the leaf-page?

Yes, assuming the column that was updated is in the index key. However, this is still a single object access, and hence a "single write."

share|improve this answer
    
I didn't quite understand your last statement. If you look at the ppt at google.co.in/… , you will find that when 5 is inserted, the 8 in the leaf level is pushed to the non-leaf level, effectively creating two copies of it. –  Cupidvogel Sep 13 '12 at 18:05
    
@Cupidvogel: I edited the answer to clarify what I meant. –  Jon Seigel Sep 13 '12 at 19:19
1  
@JonSeigel The non-leaf levels of an index just contain down-level page pointers and the minimum value that might be stored on each down-level page (NULL for the first logical page). Not every modification results in changes above the leaf, in fact most don't. –  Paul White Sep 14 '12 at 11:14
    
@SQLKiwi: Ah yes, you're correct. I've edited the answer to remove that section, as I think the point the OP needed was covered by the rest of it. –  Jon Seigel Sep 14 '12 at 13:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.