#nz8 Index b-tree interior cells contain payload (key + rowid) that is found in Index b-tree leaf cells

[ruiyigan]

Hello, I like to check my understanding on this matter. Is it true that for table b-trees, all data resides in leaf cells but for index b-trees data is stored both in the interior and leaf cells (It is stored as payload in the interior cell as key + rowid after the left pointer). And there is no duplication in data so you can’t find all the rowids in the leaf cells for index b-trees.

My reason for this conclusion is because when running ./your_program.sh companies.db "SELECT id, name FROM companies WHERE country = 'eritrea'" initially locally by just adding the rowids I get from matching key at the index leaf cells, I get the following output:

121311|unilink s.c.
2102438|orange asmara it solutions
6634629|asmara rental

However, the row 5729848|zara mining share company is missing. I still managed to pass the online test cases as I think this test case is omitted or I somehow didn’t encounter it since its random?

It is only when I also add the rowids from the payload of the interior cells where I managed to get the missing rowid (5729848).

Please correct me if I am wrong! I’m new to this as well. Thank you

[andy1li]

Hey @ruiyigan, as far as I know, you can find all data/pointers in leafs.

For example, in the case of country = 'eritrea', all 4 index pointers reside in a single leaf index page.

---

Here’s how you can manually verify it:

1. Download the full companies.db.
2. Locate the root index page (=> 223839):

3. Follow the interior index pointers:

• xxd -s916840448 -l4096 companies.db (=> 0x388a9):

• xxd -s948600832 -l4096 companies.db (=> 0x388bf):

4. Inspect the leaf index page:

• xxd -s948690944 -l4096 companies.db

5. Check that the row IDs match:

[ruiyigan]

Hi andy! Thank you for the quick response. I went to check and realized that my rootpage for idx_companies_country is 4 and my database seem to be much smaller with ending address 0x776000

I checked the readme and it says companies.db:

• This is a small version of the test database used in the index-scan stage.
• It contains one table: companies, and one index: idx_companies_country
• It is ~7MB in size.

Am I right to say that my data used locally is different from the one you have attached? (That’s the full) And for this smaller database the data exist in the interior cell instead of all in the leafs.

I went to check and I think the interior page lies in pagenumber 1849 with an offset of 7569408 so in hex 738000 and I checked I see the entry for row id of zara mining share somewhere near it as seen in the screenshot below:

Thank you!

[andy1li]

Yes, you’re absolutely right! I stand corrected.

Just checked the smaller companies.db, and confirmed that 0x576e38 resides only in the interior index page 1849.

[andy1li]

Closing this thread due to inactivity. If you still need assistance, feel free to reopen or start a new discussion!