Re: [sqlite] 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 <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
Richard Hipp <d...@sqlite.org>
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 <sc...@casaderobison.com> 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
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Richard Hipp]

On 8/11/17, Scott Robison  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
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Simon Slavin]

On 11 Aug 2017, at 4:16pm, james ni  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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Scott Robison]

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" <james...@live.cn> wrote:

> Yes, yes, that's what I'm seeking
>
> 
> From: sqlite-users <sqlite-users-boun...@mailinglists.sqlite.org> on
> behalf of R Smith <rsm...@rsweb.co.za>
> Sent: Friday, August 11, 2017 18:25
> To: sqlite-users@mailinglists.sqlite.org
> 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
> sqlite-users@mailinglists.sqlite.org
> 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
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[james ni]

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


From: sqlite-users <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
R Smith <rsm...@rsweb.co.za>
Sent: Friday, August 11, 2017 18:25
To: sqlite-users@mailinglists.sqlite.org
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
sqlite-users@mailinglists.sqlite.org
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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Niall O'Reilly]

On 11 August 2017 11:08:02 GMT+01:00, james ni  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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[R Smith]

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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Clemens Ladisch]

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: .

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


Regards,
Clemens
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] 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 <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
james ni <james...@live.cn>
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 <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
Rowan Worth <row...@dug.com>
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 <james...@live.cn> 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 <sqlite-users-boun...@mailinglists.sqlite.org> on
> behalf of Hick Gunter <h...@scigames.at>
> 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:sqlite-users-boun...@mailinglists.sqlite.org]
> Im Auftrag von ni james
> Gesendet: Freitag, 11. August 2017 04:57
> An: sqlite-users@mailinglists.sqlite.org
> 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 on

Re: [sqlite] 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 <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
Rowan Worth <row...@dug.com>
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 <james...@live.cn> 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 <sqlite-users-boun...@mailinglists.sqlite.org> on
> behalf of Hick Gunter <h...@scigames.at>
> 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:sqlite-users-boun...@mailinglists.sqlite.org]
> Im Auftrag von ni james
> Gesendet: Freitag, 11. August 2017 04:57
> An: sqlite-users@mailinglists.sqlite.org
> 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!
>
> _

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

[Rowan Worth]

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 <james...@live.cn> 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 <sqlite-users-boun...@mailinglists.sqlite.org> on
> behalf of Hick Gunter <h...@scigames.at>
> 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:sqlite-users-boun...@mailinglists.sqlite.org]
> Im Auftrag von ni james
> Gesendet: Freitag, 11. August 2017 04:57
> An: sqlite-users@mailinglists.sqlite.org
> 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
> sqlite-users@mailinglists.sqlite.org
> 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: h...@scigames.at
>
> 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
> b

Re: [sqlite] 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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] 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 <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
Hick Gunter <h...@scigames.at>
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:sqlite-users-boun...@mailinglists.sqlite.org] Im 
Auftrag von ni james
Gesendet: Freitag, 11. August 2017 04:57
An: sqlite-users@mailinglists.sqlite.org
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
sqlite-users@mailinglists.sqlite.org
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: h...@scigames.at

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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Hick Gunter]

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:sqlite-users-boun...@mailinglists.sqlite.org] Im 
Auftrag von ni james
Gesendet: Freitag, 11. August 2017 04:57
An: sqlite-users@mailinglists.sqlite.org
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
sqlite-users@mailinglists.sqlite.org
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: h...@scigames.at

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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[james ni]

0001000: 0a00  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 <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
Clemens Ladisch <clem...@ladisch.de>
Sent: Friday, August 11, 2017 14:41
To: sqlite-users@mailinglists.sqlite.org
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
sqlite-users@mailinglists.sqlite.org
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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] 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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users