SQLite Forum

find in b+-tree node
Login

find in b+-tree node

(1) By sqlite3_preupdate_count (XiongZaiBingGan) on 2021-04-12 03:23:41 [link] [source]

My test environment is:

#create table test (name text,age int);

#create index idx on test(name);

#table test include a record (name:'tom',age:32). My confusion is when I apply the following statement,how sqlite match the record and the b+-tree node which include the record ? statement:select * from test where name='tom';

First,I say my understanding, but I'm not sure if it's correct, so I hope you can confirm it for me. If there are any mistakes, please correct them。

##My understanding is :vm engine use tree-module service,tell tree-module vm want to get record which name='tom'.tree-module first do binary-search in a b-tree (which holds the content of the index of table test) to find rowid,then do a binary-search in b+tree (which holds the records of the table test) by rowid.

when get rowid,how to map the rowid to tree-node which include the rowid?

(2) By Larry Brasfield (larrybr) on 2021-04-12 03:28:03 in reply to 1 [link] [source]

Once the rowid has been obtained from the index, it is used to perform a binary search on the b-tree which constitutes table test. For ordinary tables, (those which are not WITHOUT ROWID tables), the rowid is the key by which the b-tree is ordered.

(3) By sqlite3_preupdate_count (XiongZaiBingGan) on 2021-04-12 03:51:29 in reply to 2 [link] [source]

I don't describe it clearly enough,i want to know when get rowid,how to use the rowid to get record from b+tree node ? I think b+tree node is a page,a page contains many records.how sqlite know rowid in which b+tree node?

(4) By Richard Hipp (drh) on 2021-04-12 11:31:21 in reply to 3 [link] [source]

The rows on the b+tree page are in sorted order - sorted by rowid. The database engine does a binary search of those rows to find the specific row with the rowid you are looking for.

(5) By Bill Wade (billwade) on 2021-04-12 12:28:12 in reply to 1 [source]

When your query is

select * from test where name='tom';

It is likely that the database engine is answering that by doing something similar to:

select * from test where rowid = (select rowid from test where name='tom');

Your index on name is used to answer the inner query. The primary key index on rowid is used to answer the outer query.

However, your original query did all that for you. For this example, you didn't explicitly need to know anything about rowid, or any tree-node (or even to know that those things were used in the implementation).

In principle, SQLite, might notice that the test table is small enough that using the index won't speed things up, and thus decide to avoid it entirely. All you are supposed to care about is that the query was performed correctly and efficiently.