does incremented column makes the b-tree index on the column unbalanced?

Question

I have been thinking about two questions. Couldn't find any resources on the internet about this. How do dbms handle it ? Or do they ? Especially Oracle.

Before the questions, here is an example: Say I have a master table "MASTER" and slave table "SLAVE". Master table has an "ID" column which is the primary key and index is created by Oracle.Slave table has the foreign key "MASTER_ID" which refers to master table and "SLAVE_NO". These two together is the primary key of slave table, which is again indexed.

 **MASTER**  |  **SLAVE**
     (P) ID <------> (P)(F) MASTER_ID 
                     (P) SLAVE_NO

Now the questions;

1- If MASTER_ID is an autoincremented column, and no record is ever deleted, doesn't this get the table's index unbalanced ? Does Oracle rebuilds indexes periodically ? As far as i know Oracle only balances index branches at build time. Does Oracle re-builds indexes Automatically ever ? Say if the level goes up to some high levels ?

2- Assuming Oracle does not rebuild automatically, apart from scheduling a job that rebuilds index periodically, would it be wiser to order SLAVE table's primary key columns reverse ? I mean instead of "MASTER_ID", "SLAVE_NO" ordering it as "SLAVE_NO", "MASTER_ID"i, would it help the slave table's b-tree index be more balanced ? (Well each master table might not have exact number of slave records, but still, seems better than reverse order)

Anyone know anything about that ? Or opinions ?

Answer 1

If MASTER_ID is an autoincremented column, and no record is ever deleted, doesn't this get the table's index unbalanced ?

Oracle's indexes are never "unbalanced": every leaf in the index is at the same depth as any other leaf.

No page split introduces a new level by itself: a leaf page does not become a parent for new pages like it would be on a non-self-balancing tree.

Instead, a sibling for the split page is made and the new record (plus possibly some of the records from the old page) go to the new page. A pointer to the new page is added to the parent.

If the parent page is out of space too (can't accept the pointer to the newly created leaf page), it gets split as well, and so on.

These splits can propagate up to the root page, whose split is the only thing which increases the index depth (and does it for all pages at once).

Index pages are additionally organized into double-linked lists, each list on its own level. This would be impossible if the tree were unbalanced.

If master_id is auto-incremented this means that all splits occur at the end (such called 90/10 splits) which makes the most dense index possible.

Would it be wiser to order SLAVE table's primary key columns reverse?

No, it would not, for the reasons above.

If you join slave to master often, you may consider creating a CLUSTER of the two tables, indexed by master_id. This means that the records from both tables, sharing the same master_id, go to the same or nearby data pages which makes a join between them very fast.

When the engine found a record from master, with an index or whatever, this also means it already has found the records from slave to be joined with that master. And vice versa, locating a slave also means locating its master.