When a record is inserted, it's first hashed to a bucket number.
The primary page of that bucket is
brought in and the overflow page number on that page is checked. If
there is an overflow page, it's brought in and the overflow page is
checked again until the last page is brought in. Since all bucket
pages are compact, the record will be inserted to the last slot on
the last page. However, if the last page is full, then a new page is
allocated to store the new record and a split is triggered.
When a split is triggered, two new bucket pages are allocated. All the
records in the next bucket are redistributed to the 2 new buckets
and overflow pages are allocated if necessary. Then the old bucket is
deallocated and the corresponding header information is updated.