What's the level of B+-Tree ?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

What's the level of B+-Tree ?

james ni
In the "SQLite File Format" document, the BTree layout is described, but now I want to know how to get the BTree level (which is the 'K' value mentioned in the Documentation)?


Generally, one B+Tree segment contains K keys and (K+1) pointers to child segments.


From the source code, I found such info:


/*
** This constant controls how often segments are merged. Once there are
** FTS3_MERGE_COUNT segments of level N, they are merged into a single
** segment of level N+1.
*/
#define FTS3_MERGE_COUNT 16

....

/*
** FTS4 virtual tables may maintain multiple indexes - one index of all terms
** in the document set and zero or more prefix indexes. All indexes are stored
** as one or more b+-trees in the %_segments and %_segdir tables.
**
** It is possible to determine which index a b+-tree belongs to based on the
** value stored in the "%_segdir.level" column. Given this value L, the index
** that the b+-tree belongs to is (L<<10). In other words, all b+-trees with
** level values between 0 and 1023 (inclusive) belong to index 0, all levels
** between 1024 and 2047 to index 1, and so on.
**
** It is considered impossible for an index to use more than 1024 levels. In
** theory though this may happen, but only after at least
** (FTS3_MERGE_COUNT^1024) separate flushes of the pending-terms tables.
*/
#define FTS3_SEGDIR_MAXLEVEL 1024
#define FTS3_SEGDIR_MAXLEVEL_STR "1024"


It seems the BTree level is 16 or 1024 ??


Would any one share you knowledge on how to get this value ?

Much appreciated if you can tell how to tune this value.


Thanks!

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Clemens Ladisch
ni james wrote:
> In the "SQLite File Format" document, the BTree layout is described,
> but now I want to know how to get the BTree level (which is the 'K'
> value mentioned in the Documentation)?

At the end of section 1.5, a "K" is defined.  But I don't think that is
the same K.

Anyway, the document also says:
| The cell pointer array of a b-tree page immediately follows the b-tree
| page header. Let K be the number of cells on the btree. The cell
| pointer array consists of K 2-byte integer offsets to the cell
| contents.

The number of cells in the page is found at offset 3 in the b-tree page
header.


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

james ni

0001000: 0a00 0000 040f 9000 0f90 0fc8 0fac 0fe4  ................


So there are 4 cells in this btree page. But that's not what I'm seeking....

I want to know the level of the BTree, don't know if "level" is the exact term to express my idea, let's see in this:


A cell in the BTree is comprised of n keys and (n+1) pointers to its children, the layout is like this:

(pointer0, key1, pointer1, key2, pointer2, ... , keyn, pointern)


What I want to know is how to get the value of "n" ?

And how to tune this value ?


Because in my development, I found there are plenty of disk IO access during INSERT when one table grows larger. So I suspect the value of "n" should be much smaller.

________________________________
From: sqlite-users <[hidden email]> on behalf of Clemens Ladisch <[hidden email]>
Sent: Friday, August 11, 2017 14:41
To: [hidden email]
Subject: Re: [sqlite] What's the level of B+-Tree ?

ni james wrote:
> In the "SQLite File Format" document, the BTree layout is described,
> but now I want to know how to get the BTree level (which is the 'K'
> value mentioned in the Documentation)?

At the end of section 1.5, a "K" is defined.  But I don't think that is
the same K.

Anyway, the document also says:
| The cell pointer array of a b-tree page immediately follows the b-tree
| page header. Let K be the number of cells on the btree. The cell
| pointer array consists of K 2-byte integer offsets to the cell
| contents.

The number of cells in the page is found at offset 3 in the b-tree page
header.


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
sqlite-users Info Page<http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users>
mailinglists.sqlite.org
To see the collection of prior postings to the list, visit the sqlite-users Archives. (The current archive is only available to the list ...


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Hick Gunter
In reply to this post by james ni
The number of keys in an sqlite index page depends on the size of the database pages and the size of the (compressed) key value, which is stored in the same "row format" as the data.

Child segment pointers are stored at the beginning of the page and key contents are stored at the end. The page is full, when the unallocated space in between these areas becomes too small to store enything useful. Note that key contents may change in length if a key field is updated, so the key contents area may become fragmented (sqlite willl defragment the page if needed).

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von ni james
Gesendet: Freitag, 11. August 2017 04:57
An: [hidden email]
Betreff: [sqlite] What's the level of B+-Tree ?

In the "SQLite File Format" document, the BTree layout is described, but now I want to know how to get the BTree level (which is the 'K' value mentioned in the Documentation)?


Generally, one B+Tree segment contains K keys and (K+1) pointers to child segments.


From the source code, I found such info:


/*
** This constant controls how often segments are merged. Once there are
** FTS3_MERGE_COUNT segments of level N, they are merged into a single
** segment of level N+1.
*/
#define FTS3_MERGE_COUNT 16

....

/*
** FTS4 virtual tables may maintain multiple indexes - one index of all terms
** in the document set and zero or more prefix indexes. All indexes are stored
** as one or more b+-trees in the %_segments and %_segdir tables.
**
** It is possible to determine which index a b+-tree belongs to based on the
** value stored in the "%_segdir.level" column. Given this value L, the index
** that the b+-tree belongs to is (L<<10). In other words, all b+-trees with
** level values between 0 and 1023 (inclusive) belong to index 0, all levels
** between 1024 and 2047 to index 1, and so on.
**
** It is considered impossible for an index to use more than 1024 levels. In
** theory though this may happen, but only after at least
** (FTS3_MERGE_COUNT^1024) separate flushes of the pending-terms tables.
*/
#define FTS3_SEGDIR_MAXLEVEL 1024
#define FTS3_SEGDIR_MAXLEVEL_STR "1024"


It seems the BTree level is 16 or 1024 ??


Would any one share you knowledge on how to get this value ?

Much appreciated if you can tell how to tune this value.


Thanks!

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

james ni
Thanks, but I'm more confused now.


As in the example that I provided, there are 4 cells in a single btree page. So there must be some mechanism to determine hoe many keys that one cell can own.


I want to know exactly the very value and just how to change the value to a larger one, for example, 256, 512, or even larger.

________________________________
From: sqlite-users <[hidden email]> on behalf of Hick Gunter <[hidden email]>
Sent: Friday, August 11, 2017 16:31
To: 'SQLite mailing list'
Subject: Re: [sqlite] What's the level of B+-Tree ?

The number of keys in an sqlite index page depends on the size of the database pages and the size of the (compressed) key value, which is stored in the same "row format" as the data.

Child segment pointers are stored at the beginning of the page and key contents are stored at the end. The page is full, when the unallocated space in between these areas becomes too small to store enything useful. Note that key contents may change in length if a key field is updated, so the key contents area may become fragmented (sqlite willl defragment the page if needed).

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von ni james
Gesendet: Freitag, 11. August 2017 04:57
An: [hidden email]
Betreff: [sqlite] What's the level of B+-Tree ?

In the "SQLite File Format" document, the BTree layout is described, but now I want to know how to get the BTree level (which is the 'K' value mentioned in the Documentation)?


Generally, one B+Tree segment contains K keys and (K+1) pointers to child segments.


From the source code, I found such info:


/*
** This constant controls how often segments are merged. Once there are
** FTS3_MERGE_COUNT segments of level N, they are merged into a single
** segment of level N+1.
*/
#define FTS3_MERGE_COUNT 16

....

/*
** FTS4 virtual tables may maintain multiple indexes - one index of all terms
** in the document set and zero or more prefix indexes. All indexes are stored
** as one or more b+-trees in the %_segments and %_segdir tables.
**
** It is possible to determine which index a b+-tree belongs to based on the
** value stored in the "%_segdir.level" column. Given this value L, the index
** that the b+-tree belongs to is (L<<10). In other words, all b+-trees with
** level values between 0 and 1023 (inclusive) belong to index 0, all levels
** between 1024 and 2047 to index 1, and so on.
**
** It is considered impossible for an index to use more than 1024 levels. In
** theory though this may happen, but only after at least
** (FTS3_MERGE_COUNT^1024) separate flushes of the pending-terms tables.
*/
#define FTS3_SEGDIR_MAXLEVEL 1024
#define FTS3_SEGDIR_MAXLEVEL_STR "1024"


It seems the BTree level is 16 or 1024 ??


Would any one share you knowledge on how to get this value ?

Much appreciated if you can tell how to tune this value.


Thanks!

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Clemens Ladisch
james ni wrote:
> As in the example that I provided, there are 4 cells in a single btree
> page. So there must be some mechanism to determine hoe many keys that
> one cell can own.

One key per cell:
| Within an interior b-tree page, each key and the pointer to its
| immediate left are combined into a structure called a "cell". The
| right-most pointer is held separately.

> I want to know exactly the very value and just how to change the value
> to a larger one, for example, 256, 512, or even larger.

Keys (and values) can have arbitrary size, so to change how many can fit
into a page, make them smaller.  :)


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Rowan Worth-2
In reply to this post by james ni
Jump to the byte offset specified by the "start of the cell content"
header, which comes just after the number of pages (ie. offset 0x0f90 in
your pasted example).

Cross reference the data at that offset against section "2.1 Record Format"
of the Database File Format page. By decoding the record header you know
how many columns are in that particular index record (which might not match
the number of columns are in the table, as noted in the spec).

Is that what you're after? Or are you trying to figure out the depth of a
particular btree page?

-Rowan

On 11 August 2017 at 16:51, james ni <[hidden email]> wrote:

> Thanks, but I'm more confused now.
>
>
> As in the example that I provided, there are 4 cells in a single btree
> page. So there must be some mechanism to determine hoe many keys that one
> cell can own.
>
>
> I want to know exactly the very value and just how to change the value to
> a larger one, for example, 256, 512, or even larger.
>
> ________________________________
> From: sqlite-users <[hidden email]> on
> behalf of Hick Gunter <[hidden email]>
> Sent: Friday, August 11, 2017 16:31
> To: 'SQLite mailing list'
> Subject: Re: [sqlite] What's the level of B+-Tree ?
>
> The number of keys in an sqlite index page depends on the size of the
> database pages and the size of the (compressed) key value, which is stored
> in the same "row format" as the data.
>
> Child segment pointers are stored at the beginning of the page and key
> contents are stored at the end. The page is full, when the unallocated
> space in between these areas becomes too small to store enything useful.
> Note that key contents may change in length if a key field is updated, so
> the key contents area may become fragmented (sqlite willl defragment the
> page if needed).
>
> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]]
> Im Auftrag von ni james
> Gesendet: Freitag, 11. August 2017 04:57
> An: [hidden email]
> Betreff: [sqlite] What's the level of B+-Tree ?
>
> In the "SQLite File Format" document, the BTree layout is described, but
> now I want to know how to get the BTree level (which is the 'K' value
> mentioned in the Documentation)?
>
>
> Generally, one B+Tree segment contains K keys and (K+1) pointers to child
> segments.
>
>
> From the source code, I found such info:
>
>
> /*
> ** This constant controls how often segments are merged. Once there are
> ** FTS3_MERGE_COUNT segments of level N, they are merged into a single
> ** segment of level N+1.
> */
> #define FTS3_MERGE_COUNT 16
>
> ....
>
> /*
> ** FTS4 virtual tables may maintain multiple indexes - one index of all
> terms
> ** in the document set and zero or more prefix indexes. All indexes are
> stored
> ** as one or more b+-trees in the %_segments and %_segdir tables.
> **
> ** It is possible to determine which index a b+-tree belongs to based on
> the
> ** value stored in the "%_segdir.level" column. Given this value L, the
> index
> ** that the b+-tree belongs to is (L<<10). In other words, all b+-trees
> with
> ** level values between 0 and 1023 (inclusive) belong to index 0, all
> levels
> ** between 1024 and 2047 to index 1, and so on.
> **
> ** It is considered impossible for an index to use more than 1024 levels.
> In
> ** theory though this may happen, but only after at least
> ** (FTS3_MERGE_COUNT^1024) separate flushes of the pending-terms tables.
> */
> #define FTS3_SEGDIR_MAXLEVEL 1024
> #define FTS3_SEGDIR_MAXLEVEL_STR "1024"
>
>
> It seems the BTree level is 16 or 1024 ??
>
>
> Would any one share you knowledge on how to get this value ?
>
> Much appreciated if you can tell how to tune this value.
>
>
> Thanks!
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___________________________________________
>  Gunter Hick
> Software Engineer
> Scientific Games International GmbH
> FN 157284 a, HG Wien
> Klitschgasse 2-4, A-1130 Vienna, Austria
> Tel: +43 1 80100 0
> E-Mail: [hidden email]
>
> This communication (including any attachments) is intended for the use of
> the intended recipient(s) only and may contain information that is
> confidential, privileged or legally protected. Any unauthorized use or
> dissemination of this communication is strictly prohibited. If you have
> received this communication in error, please immediately notify the sender
> by return e-mail message and delete all copies of the original
> communication. Thank you for your cooperation.
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

james ni
Maybe we are talking the different thing.


Background of my problem:

1, When one table grows larger, I found the INSERT speed is becoming slower and slower;


2, My task is to make it not so slower;


3, The linux perf tool shows the BTree depth is likely growing larger and larger after more records are inserted because the number of syscalls are increasing quickly;


4, So I want to know the how many keys can be stored in a Btree node. The more keys that a Btree node can hold, the shorter of the Btree depth, the less syscalls and disk IOs;


That's what i want to know.

________________________________
From: sqlite-users <[hidden email]> on behalf of Rowan Worth <[hidden email]>
Sent: Friday, August 11, 2017 17:09
To: SQLite mailing list
Subject: Re: [sqlite] What's the level of B+-Tree ?

Jump to the byte offset specified by the "start of the cell content"
header, which comes just after the number of pages (ie. offset 0x0f90 in
your pasted example).

Cross reference the data at that offset against section "2.1 Record Format"
of the Database File Format page. By decoding the record header you know
how many columns are in that particular index record (which might not match
the number of columns are in the table, as noted in the spec).

Is that what you're after? Or are you trying to figure out the depth of a
particular btree page?

-Rowan

On 11 August 2017 at 16:51, james ni <[hidden email]> wrote:

> Thanks, but I'm more confused now.
>
>
> As in the example that I provided, there are 4 cells in a single btree
> page. So there must be some mechanism to determine hoe many keys that one
> cell can own.
>
>
> I want to know exactly the very value and just how to change the value to
> a larger one, for example, 256, 512, or even larger.
>
> ________________________________
> From: sqlite-users <[hidden email]> on
> behalf of Hick Gunter <[hidden email]>
> Sent: Friday, August 11, 2017 16:31
> To: 'SQLite mailing list'
> Subject: Re: [sqlite] What's the level of B+-Tree ?
>
> The number of keys in an sqlite index page depends on the size of the
> database pages and the size of the (compressed) key value, which is stored
> in the same "row format" as the data.
>
> Child segment pointers are stored at the beginning of the page and key
> contents are stored at the end. The page is full, when the unallocated
> space in between these areas becomes too small to store enything useful.
> Note that key contents may change in length if a key field is updated, so
> the key contents area may become fragmented (sqlite willl defragment the
> page if needed).
>
> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]]
> Im Auftrag von ni james
> Gesendet: Freitag, 11. August 2017 04:57
> An: [hidden email]
> Betreff: [sqlite] What's the level of B+-Tree ?
>
> In the "SQLite File Format" document, the BTree layout is described, but
> now I want to know how to get the BTree level (which is the 'K' value
> mentioned in the Documentation)?
>
>
> Generally, one B+Tree segment contains K keys and (K+1) pointers to child
> segments.
>
>
> From the source code, I found such info:
>
>
> /*
> ** This constant controls how often segments are merged. Once there are
> ** FTS3_MERGE_COUNT segments of level N, they are merged into a single
> ** segment of level N+1.
> */
> #define FTS3_MERGE_COUNT 16
>
> ....
>
> /*
> ** FTS4 virtual tables may maintain multiple indexes - one index of all
> terms
> ** in the document set and zero or more prefix indexes. All indexes are
> stored
> ** as one or more b+-trees in the %_segments and %_segdir tables.
> **
> ** It is possible to determine which index a b+-tree belongs to based on
> the
> ** value stored in the "%_segdir.level" column. Given this value L, the
> index
> ** that the b+-tree belongs to is (L<<10). In other words, all b+-trees
> with
> ** level values between 0 and 1023 (inclusive) belong to index 0, all
> levels
> ** between 1024 and 2047 to index 1, and so on.
> **
> ** It is considered impossible for an index to use more than 1024 levels.
> In
> ** theory though this may happen, but only after at least
> ** (FTS3_MERGE_COUNT^1024) separate flushes of the pending-terms tables.
> */
> #define FTS3_SEGDIR_MAXLEVEL 1024
> #define FTS3_SEGDIR_MAXLEVEL_STR "1024"
>
>
> It seems the BTree level is 16 or 1024 ??
>
>
> Would any one share you knowledge on how to get this value ?
>
> Much appreciated if you can tell how to tune this value.
>
>
> Thanks!
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___________________________________________
>  Gunter Hick
> Software Engineer
> Scientific Games International GmbH
> FN 157284 a, HG Wien
> Klitschgasse 2-4, A-1130 Vienna, Austria
> Tel: +43 1 80100 0
> E-Mail: [hidden email]
>
> This communication (including any attachments) is intended for the use of
> the intended recipient(s) only and may contain information that is
> confidential, privileged or legally protected. Any unauthorized use or
> dissemination of this communication is strictly prohibited. If you have
> received this communication in error, please immediately notify the sender
> by return e-mail message and delete all copies of the original
> communication. Thank you for your cooperation.
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

james ni
Let's don't focus on the "file format" documentation, just focus on the BTree algorithm.


I want to know the depth of the BTree, and how to reduce the depth of it.


________________________________
From: sqlite-users <[hidden email]> on behalf of james ni <[hidden email]>
Sent: Friday, August 11, 2017 18:08
To: SQLite mailing list
Subject: Re: [sqlite] What's the level of B+-Tree ?

Maybe we are talking the different thing.


Background of my problem:

1, When one table grows larger, I found the INSERT speed is becoming slower and slower;


2, My task is to make it not so slower;


3, The linux perf tool shows the BTree depth is likely growing larger and larger after more records are inserted because the number of syscalls are increasing quickly;


4, So I want to know the how many keys can be stored in a Btree node. The more keys that a Btree node can hold, the shorter of the Btree depth, the less syscalls and disk IOs;


That's what i want to know.

________________________________
From: sqlite-users <[hidden email]> on behalf of Rowan Worth <[hidden email]>
Sent: Friday, August 11, 2017 17:09
To: SQLite mailing list
Subject: Re: [sqlite] What's the level of B+-Tree ?

Jump to the byte offset specified by the "start of the cell content"
header, which comes just after the number of pages (ie. offset 0x0f90 in
your pasted example).

Cross reference the data at that offset against section "2.1 Record Format"
of the Database File Format page. By decoding the record header you know
how many columns are in that particular index record (which might not match
the number of columns are in the table, as noted in the spec).

Is that what you're after? Or are you trying to figure out the depth of a
particular btree page?

-Rowan

On 11 August 2017 at 16:51, james ni <[hidden email]> wrote:

> Thanks, but I'm more confused now.
>
>
> As in the example that I provided, there are 4 cells in a single btree
> page. So there must be some mechanism to determine hoe many keys that one
> cell can own.
>
>
> I want to know exactly the very value and just how to change the value to
> a larger one, for example, 256, 512, or even larger.
>
> ________________________________
> From: sqlite-users <[hidden email]> on
> behalf of Hick Gunter <[hidden email]>
> Sent: Friday, August 11, 2017 16:31
> To: 'SQLite mailing list'
> Subject: Re: [sqlite] What's the level of B+-Tree ?
>
> The number of keys in an sqlite index page depends on the size of the
> database pages and the size of the (compressed) key value, which is stored
> in the same "row format" as the data.
>
> Child segment pointers are stored at the beginning of the page and key
> contents are stored at the end. The page is full, when the unallocated
> space in between these areas becomes too small to store enything useful.
> Note that key contents may change in length if a key field is updated, so
> the key contents area may become fragmented (sqlite willl defragment the
> page if needed).
>
> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]]
> Im Auftrag von ni james
> Gesendet: Freitag, 11. August 2017 04:57
> An: [hidden email]
> Betreff: [sqlite] What's the level of B+-Tree ?
>
> In the "SQLite File Format" document, the BTree layout is described, but
> now I want to know how to get the BTree level (which is the 'K' value
> mentioned in the Documentation)?
>
>
> Generally, one B+Tree segment contains K keys and (K+1) pointers to child
> segments.
>
>
> From the source code, I found such info:
>
>
> /*
> ** This constant controls how often segments are merged. Once there are
> ** FTS3_MERGE_COUNT segments of level N, they are merged into a single
> ** segment of level N+1.
> */
> #define FTS3_MERGE_COUNT 16
>
> ....
>
> /*
> ** FTS4 virtual tables may maintain multiple indexes - one index of all
> terms
> ** in the document set and zero or more prefix indexes. All indexes are
> stored
> ** as one or more b+-trees in the %_segments and %_segdir tables.
> **
> ** It is possible to determine which index a b+-tree belongs to based on
> the
> ** value stored in the "%_segdir.level" column. Given this value L, the
> index
> ** that the b+-tree belongs to is (L<<10). In other words, all b+-trees
> with
> ** level values between 0 and 1023 (inclusive) belong to index 0, all
> levels
> ** between 1024 and 2047 to index 1, and so on.
> **
> ** It is considered impossible for an index to use more than 1024 levels.
> In
> ** theory though this may happen, but only after at least
> ** (FTS3_MERGE_COUNT^1024) separate flushes of the pending-terms tables.
> */
> #define FTS3_SEGDIR_MAXLEVEL 1024
> #define FTS3_SEGDIR_MAXLEVEL_STR "1024"
>
>
> It seems the BTree level is 16 or 1024 ??
>
>
> Would any one share you knowledge on how to get this value ?
>
> Much appreciated if you can tell how to tune this value.
>
>
> Thanks!
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___________________________________________
>  Gunter Hick
> Software Engineer
> Scientific Games International GmbH
> FN 157284 a, HG Wien
> Klitschgasse 2-4, A-1130 Vienna, Austria
> Tel: +43 1 80100 0
> E-Mail: [hidden email]
>
> This communication (including any attachments) is intended for the use of
> the intended recipient(s) only and may contain information that is
> confidential, privileged or legally protected. Any unauthorized use or
> dissemination of this communication is strictly prohibited. If you have
> received this communication in error, please immediately notify the sender
> by return e-mail message and delete all copies of the original
> communication. Thank you for your cooperation.
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Clemens Ladisch
In reply to this post by james ni
james ni wrote:
> the INSERT speed is becoming slower and slower;
>
> the number of syscalls are increasing quickly;

Insert the largest values last.

Increase the cache size: <http://www.sqlite.org/pragma.html#pragma_cache_size>.

Decrease the amount of data stored in the index.  (This is unlikely to
be possible.)


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

R Smith
In reply to this post by Clemens Ladisch

On 2017/08/11 11:08 AM, Clemens Ladisch wrote:
> james ni wrote:
>> As in the example that I provided, there are 4 cells in a single btree
>> page. So there must be some mechanism to determine hoe many keys that
>> one cell can own.
> I want to know exactly the very value and just how to change the value
> to a larger one, for example, 256, 512, or even larger.
> Keys (and values) can have arbitrary size, so to change how many can fit
> into a page, make them smaller.  :)

I think perhaps there is a communication failure here. I think the OP is
looking for a way to change the target key count or maximum allowed keys
or whatever other value controls how wide a B-Tree page/leaf becomes
before SQLite decides to de-congest it into two/more new apartments
(whatever they may be). I /think/ that's what is being asked.

If that is the question - I'm not an expert on it, but I don't think it
works like that. I think DB Page-sizes dictate those decisions, but I
might well be wrong.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Niall O'Reilly
In reply to this post by james ni
On 11 August 2017 11:08:02 GMT+01:00, james ni <[hidden email]> wrote:
>Maybe we are talking the different thing.
>
>
>Background of my problem:
>
>1, When one table grows larger, I found the INSERT speed is becoming
>slower and slower;

It seems to me that you may have chosen to view the problem from an angle which will hide the solution.

I had a similar problem in a previous job. I had data arriving from a logging system with multiple events per second. This data had to be parsed and loaded into an SQLite db.

At first, I retrieved log data every five minutes and ran an INSERT for each log entry. This "just worked" for a week or so. Then I noticed that elapsed time was growing. Advice from this list encouraged me to enclose multiple INSERT commands in a single transaction. The results were dramatically effective, although I should mention that this was not the only design optimization I needed.

If my use case is actually similar to yours, I'ld suggest you try this too.

Best regards,
Niall O'Reilly


--
Sent from Kaiten Mail. Please excuse my brevity.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

james ni
In reply to this post by R Smith
Yes, yes, that's what I'm seeking....

________________________________
From: sqlite-users <[hidden email]> on behalf of R Smith <[hidden email]>
Sent: Friday, August 11, 2017 18:25
To: [hidden email]
Subject: Re: [sqlite] What's the level of B+-Tree ?


On 2017/08/11 11:08 AM, Clemens Ladisch wrote:
> james ni wrote:
>> As in the example that I provided, there are 4 cells in a single btree
>> page. So there must be some mechanism to determine hoe many keys that
>> one cell can own.
> I want to know exactly the very value and just how to change the value
> to a larger one, for example, 256, 512, or even larger.
> Keys (and values) can have arbitrary size, so to change how many can fit
> into a page, make them smaller.  :)

I think perhaps there is a communication failure here. I think the OP is
looking for a way to change the target key count or maximum allowed keys
or whatever other value controls how wide a B-Tree page/leaf becomes
before SQLite decides to de-congest it into two/more new apartments
(whatever they may be). I /think/ that's what is being asked.

If that is the question - I'm not an expert on it, but I don't think it
works like that. I think DB Page-sizes dictate those decisions, but I
might well be wrong.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
sqlite-users Info Page<http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users>
mailinglists.sqlite.org
To see the collection of prior postings to the list, visit the sqlite-users Archives. (The current archive is only available to the list ...


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Scott Robison-2
My understanding is that SQLite doesn't use the traditional definition of
b-tree because it doesn't use fixed size records/keys. It will cram as few
or as many as possible.

I'm not in a position to confirm that, but it was something I read a few
years ago I think.

On Aug 11, 2017 9:16 AM, "james ni" <[hidden email]> wrote:

> Yes, yes, that's what I'm seeking....
>
> ________________________________
> From: sqlite-users <[hidden email]> on
> behalf of R Smith <[hidden email]>
> Sent: Friday, August 11, 2017 18:25
> To: [hidden email]
> Subject: Re: [sqlite] What's the level of B+-Tree ?
>
>
> On 2017/08/11 11:08 AM, Clemens Ladisch wrote:
> > james ni wrote:
> >> As in the example that I provided, there are 4 cells in a single btree
> >> page. So there must be some mechanism to determine hoe many keys that
> >> one cell can own.
> > I want to know exactly the very value and just how to change the value
> > to a larger one, for example, 256, 512, or even larger.
> > Keys (and values) can have arbitrary size, so to change how many can fit
> > into a page, make them smaller.  :)
>
> I think perhaps there is a communication failure here. I think the OP is
> looking for a way to change the target key count or maximum allowed keys
> or whatever other value controls how wide a B-Tree page/leaf becomes
> before SQLite decides to de-congest it into two/more new apartments
> (whatever they may be). I /think/ that's what is being asked.
>
> If that is the question - I'm not an expert on it, but I don't think it
> works like that. I think DB Page-sizes dictate those decisions, but I
> might well be wrong.
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> sqlite-users Info Page<http://mailinglists.sqlite.org/cgi-bin/mailman/
> listinfo/sqlite-users>
> mailinglists.sqlite.org
> To see the collection of prior postings to the list, visit the
> sqlite-users Archives. (The current archive is only available to the list
> ...
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Simon Slavin-3
In reply to this post by james ni


On 11 Aug 2017, at 4:16pm, james ni <[hidden email]> wrote:

> Yes, yes, that's what I'm seeking....

What is it that you’re ultimately trying to do with this information ?  Are you doing research on the file format for forensic purposes ?  Are you trying to edit the database file without using the SQLite library ?

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

Richard Hipp-3
In reply to this post by Scott Robison-2
On 8/11/17, Scott Robison <[hidden email]> wrote:
> My understanding is that SQLite doesn't use the traditional definition of
> b-tree because it doesn't use fixed size records/keys. It will cram as few
> or as many as possible.

Correct.

More records crammed into one page means that fewer pages need to be
read, which makes things run faster.  It also means that less disk
space gets used.

The in-tree portion of each record is size limited to ensure that at
least four records fit on each page.  Otherwise, the btree might
degenerate into a linked list.  The tail of records that exceed the
maximum in-tree record size is written onto overflow pages.

For ordinary rowid tables, a traditional b-tree is used, which means
that only the key is stored on intermediate pages and all the content
appears in the leaves.  Since the keys are always just a rowid and
typically take only a few bytes, there are ordinarily a large number
keys per page.  You can run the sqlite3_analyzer.exe utility program
(available in the "sqlite-tools-*" bundles on the
https://sqlite.org/download.html page) to see the average number of
keys/page for each table and index.  Or you can use the DBSTAT virtual
table (https://www.sqlite.org/dbstat.html) to query for that
information on a page-by-page basis.

For indexes and WITHOUT ROWID tables, the keys can be much larger, and
so the minimum-four-per-page rule is more likely to come into play.
--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the level of B+-Tree ?

james ni
Thanks Rick, it's much helpful for me.


After some experiments on the internal dbstat table, I have such conclusions, much appreciate if you would review them:


1, My working Background:

one WITHOUT ROWID table, this table's primary key is 30 bytes;

dbstat shows there are at most 110 cells in an internal Btree page;

Every page size is 4096 Bytes.


2, My conclusion:

2.1, The depth of this Btree is determined by the maximum cells in the internal page. In details the Btree depth is log(110, total_records).


2.2, If the application searches some a key in the table, in the worst situation it will issue log(110, total_records) disk IOs.

And every disk IO size is the same as the database page size, in my example it's 4096 Bytes.


2.3, the number of cells is determined by the size of the primary key. So if I extend the page size from 4096 Bytes to 64KB, the maximum number of cells

is expected to get increased and the depth of the Btree will shrink.


Is this correct ?


Thanks & Best Regards,

James

________________________________
From: sqlite-users <[hidden email]> on behalf of Richard Hipp <[hidden email]>
Sent: Saturday, August 12, 2017 1:57
To: SQLite mailing list
Subject: Re: [sqlite] What's the level of B+-Tree ?

On 8/11/17, Scott Robison <[hidden email]> wrote:
> My understanding is that SQLite doesn't use the traditional definition of
> b-tree because it doesn't use fixed size records/keys. It will cram as few
> or as many as possible.

Correct.

More records crammed into one page means that fewer pages need to be
read, which makes things run faster.  It also means that less disk
space gets used.

The in-tree portion of each record is size limited to ensure that at
least four records fit on each page.  Otherwise, the btree might
degenerate into a linked list.  The tail of records that exceed the
maximum in-tree record size is written onto overflow pages.

For ordinary rowid tables, a traditional b-tree is used, which means
that only the key is stored on intermediate pages and all the content
appears in the leaves.  Since the keys are always just a rowid and
typically take only a few bytes, there are ordinarily a large number
keys per page.  You can run the sqlite3_analyzer.exe utility program
(available in the "sqlite-tools-*" bundles on the
https://sqlite.org/download.html page) to see the average number of
SQLite Download Page<https://sqlite.org/download.html>
sqlite.org
(4.62 MiB) A precompiled Android library containing the core SQLite together with appropriate Java bindings, ready to drop into any Android Studio project. (4.09 MiB ...


keys/page for each table and index.  Or you can use the DBSTAT virtual
table (https://www.sqlite.org/dbstat.html) to query for that
The DBSTAT Virtual Table - SQLite Home Page<https://www.sqlite.org/dbstat.html>
www.sqlite.org
The DBSTAT virtual tables is a read-only eponymous virtual table that returns information about which pages of the database files are used by which tables and indexes ...


information on a page-by-page basis.

For indexes and WITHOUT ROWID tables, the keys can be much larger, and
so the minimum-four-per-page rule is more likely to come into play.
--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
sqlite-users Info Page<http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users>
mailinglists.sqlite.org
To see the collection of prior postings to the list, visit the sqlite-users Archives. (The current archive is only available to the list ...


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users