Under construction !
Case 1: Single split - no space for itup insertion
to leaf |
|
| Old algorithm | GLI algorithm |
|---|---|
Step 1: split leaf page and insert itup into leaf1(ex) Step 2: adjust parent(internal page) for 'leaf'  Step 3: adjust parent(root page) for 'internal'  Step 4: insert link to leaf1 in internal page  Step 5: adjust parent(root page) for 'internal'  |
Step 1: split leaf page and insert itup into leaf1(ex)  Step 2: delete old link and add two link in internal page to leaf & leaf1  Step 3: adjust parent(root page) for 'internal'  |
| Case 2: Two split - no space on internal page
for insertion link to leaf1 |
|
| Old algorithm | GLI algorithm |
|---|---|
|
Step 1: split leaf page and insert itup into leaf1(ex) Step 2: adjust parent(internal page) for 'leaf' Step 3: adjust parent(root page) for 'internal' Step 4: insert link to leaf1 in internal page and split internal page  Step 5: adjust parent(root page) for 'internal'  Step 6: insert link to internal1 to internal page  |
Step 1: split leaf page and insert itup into leaf1(ex) Step 2: delete old link and add two link in internal page to leaf & leaf1, then split internal page  Step 3: delete old link and add two link in root page to internal & internal1  |