Questions tagged [btree]
BTree is a Binary Tree. Use this tag only for questions pertaining to indexes implemented on a binary tree. If you have a question about hierarchy data use the tag "hierarchy".
65
questions
1
vote
1
answer
61
views
How a B-Tree index on a columnar table would look like?
Greenplum database supports B-tree index on append-optimized columnar tables which allows UPDATE operations as well . Even though it's not a recommended practice to have index on such tables(probably ...
- 341
2
votes
1
answer
69
views
Pageinspect function bt_metap says 'index is not a btree index'
I wish to examine contents of a btree index.
However each of pageinspect's btree functions says "channel_status_pkey_index" is not a btree index
Table looks like this:
CREATE TABLE public....
- 123
1
vote
5
answers
312
views
Why do Databases use HEAP to store table data while other structure like B-tree exists?
Database Engines like MS SQL Server , PostgreSQL etc uses HEAP to store table data while using B-tree to store index data. Time complexity for most operations in B-tree is O(log n) while for HEAP it ...
- 341
0
votes
1
answer
48
views
Missing GIN support function (4 or 6) for attribute 1 of index
I have a problem creating GIN indexes in postgres 14.9 and GIN 1.3
The following is the query:
CREATE TABLE assert.test_gin(col1 func.doc_sub_type[]);
CREATE INDEX ON assert.test_gin USING gin(col1);
...
0
votes
1
answer
66
views
Multikey index in Postgres
I'm struggling to optimize on correct index creation for my data structure. I'm trying to index massive amount of data (~100B records) of json data type:
{
"email": "[email protected]&...
- 103
1
vote
1
answer
246
views
Why can't three non-unique indexes be used to enforce a unique constraint?
I have a large PostgreSQL table of 3 columns, I created a separate btree index on every single column. Then, I created a multicolumn unique constraint on the table on all the 3 columns, expecting the ...
- 11
1
vote
1
answer
153
views
InnoDB - how MySQL InnoDB pages works with underlying OS file system
I've studied and summarized how MySQL InnoDB pages works with underlying OS file system when accessing secondary storage.
Would you mind to confirm that my understanding is correct?
InnoDB store ...
- 113
0
votes
0
answers
28
views
Choosing optimal analytical representation of votes, re: btree-normal v. array v. hstore
I'm tasked with scrapping a big website with a decade-long history and for the purpose of corpus & prompt engineering it into multiple datasets of various value; in some cases, this value is not ...
- 1
2
votes
2
answers
469
views
PostgreSQL BTREE descending but insert ascending
I have a (partitioned) table in a PostgreSQL that stores events. It has the following properties:
rows are rarely deleteed
rows are frequently inserted (~ 100-200 per second, every second on average)
...
- 147
0
votes
0
answers
72
views
Locking for secondary B-tree
I implemented a heap with MVCC; that is, each tuple in the heap has a history list so that updating the tuple does not block reading. I also implemented a secondary B+ tree; that is, it stores (...
- 15
8
votes
2
answers
1k
views
Index seek to specific multi-column key, then get some rows in lexicographical order
Consider the following sample table with a multi-column index:
create table BigNumbers (
col1 tinyint not null,
col2 tinyint not null,
col3 tinyint not null,
index IX_BigNumbers ...
- 775
0
votes
1
answer
203
views
Does B-tree in InnoDB use mark-delete?
I learnt that all secondary B-trees in InnoDB store pairs of the form (search key, TID) where TID is the primary keys of the records. I have the following questions:
(1) In InnoDB, does the secondary ...
- 15
1
vote
2
answers
70
views
Concurrency Control B-Tree between Hash
I am new to transaction. When I read the book "Transactional Information Systems", it is mentioned that B-tree uses key-range locking to guarantee serializability. Is that true all accesses ...
- 15
1
vote
1
answer
257
views
Check int4range includes number using B-tree index
I have a table with two important columns: value and m_range, where value:
CREATE TABLE m_filter (
value BIGINT NOT NULL,
m_range ...
- 111
0
votes
1
answer
110
views
Does “rounding” coarse-grained timestamps in an index take advantage of Postgres B-tree deduplication?
My database has an index on a timestamp column. There are many rows that have similar timestamps — there are 50,000 rows per minute.
Postgres timestamps store microsecond-level precision but I only ...
- 101
0
votes
0
answers
62
views
Working with index-key sizes which are close to the DBMS's index-key size limit
I might need to work with relatively large (non-clustered) index keys (between 1KB to 4KB). I found that Spanner and DB2 support 8KB index-key size, MSSQL allows 1.7KB and Postgress around 2.6KB (1/3 ...
- 101
0
votes
1
answer
727
views
How do B+ Tree text (username, email) indexes work
From my understanding, MongoDB uses a B+ Tree for indexes, including for unique fields such as emails and usernames.
However, I don't understand how a string value such as an email or username gets ...
- 101
0
votes
2
answers
1k
views
PostgreSQL btree index for int with character varying (ILIKE) not working
Hello I have about 50 million forums and each forum has over 30 million topics which this is my topic structure in PostgreSQL
CREATE TABLE public.forum_topic
(
"forum" integer NOT NULL,
...
- 101
0
votes
0
answers
266
views
B-tree indexing example
I am trying to understand "how" Postgres creates the indexes using b-trees with an example.
To be specific, I am looking to understand how the b-tree will look like when the ("Name"...
- 109
0
votes
2
answers
459
views
PostgreSQL B-tree, good monotonic values?
I am creating a unique ID generator for my application. I am reading everywhere that monotonic keys make life easier for the b-tree. I generate an ID by combining a time part and a random part, the ...
- 151
0
votes
1
answer
145
views
Index on Multiple Dimensions [duplicate]
I've recently started reading the book Designing Data-Intensive Applications.
This book has revealed that I have been using indexes incorrectly, in that I didn't realize that even if I have an index ...
- 165
4
votes
2
answers
512
views
Is it possible to expose the max depth of the B-Tree behind a rowstore index or a way to see how many nodes were traversed for a particular query?
I'm personally interested in data structures and with knowing that rowstore indexes are stored with a B-Tree behind them, I'm always curious in trying to visualize what those B-Trees look like for a ...
- 38.6k
1
vote
1
answer
619
views
If a rowstore index is stored in a b-tree data structure, what kind of data structure is used for a columnstore index? [duplicate]
My understanding of how regular rowstore indexes are stored is in a type of b-tree data structure, but I was wondering because of the different nature of columnstore indexes, what type of underlying ...
- 38.6k
-1
votes
1
answer
151
views
Order of a 2-level b+tree with n-distinct (assume e.g. n=10) entries
Given a two-level clustered b+tree on a non-key attribute foodCategory (of which 10 distinct values exist), is it possible to calculate the order of the b+tree? Assuming an average 69% occupancy of ...
- 101
0
votes
1
answer
4k
views
Offset vs Where performance for pagination with index
Suppose that you have a list of millions of items, each one with a timestamp (created_at).
You also have an index on created_at DESC.
Sometimes you need to navigate through all items, ...
- 623
1
vote
0
answers
306
views
Why is PostgreSQL prefix/range search finicky?
Configuration
PostgreSQL 11.4
SET default_statistics_target=1000;
Data
The scenario is that there are "computers" each with "files", which each have path (ordered text list) unique to that ...
- 780
0
votes
2
answers
420
views
How does MySQL skip ranges (nodes) in a loose index scan?
I've read the MySQL loose index scan, and it makes sense as optimization, however, when using an example B+tree, I don't understand how nodes can be efficiently skipped, due to potential matches ...
- 380
4
votes
1
answer
989
views
How do database operations (write, update, alter) on particular cell in a table are written to disk without overwriting entire file?
When I want to write to or alter particular cell of an excel file/table using python I'll use pandas read_csv then alter value in particular cell and write back to file with to_csv. But writing back ...
- 43
3
votes
2
answers
3k
views
Containment check tstzrange @> timestamptz not using btree or gist index
Schema:
Column | Type
----------------------+--------------------------
id | integer
event_id | integer ...
- 1,224
1
vote
2
answers
3k
views
How to understand Composite Primary Key when it comes to storage (in Mysql)?
I can image how rows will be arranged in a single database page as primary key order (example an auto-increment key) after reading this post. But I wonder how it will in the case of composite primary ...
- 664
-4
votes
1
answer
37
views
About the Index in MYSQL [closed]
I have a question about indexes in MYSQL.
I have a table, DIM_BANK.
The primary key is the column ID_BANK. MySQL automatically created the an index for this with the following attributes - BTREE (...
18
votes
3
answers
15k
views
How is it possible for Hash Index not to be faster than Btree for equality lookups?
For every version of Postgres that supported hash indexing, there is a warning or note that hash indexes are "similar or slower" or "not better" than btree indexes, at least up to version 8.3. From ...
- 295
3
votes
1
answer
943
views
Choosing index fillfactor for large, highly inserted table
We have a table that will hold records on the 108 order.
╔══════════╦═════╦══════╦══════════════════════════╗
║ id ║ a ║ b ║ ...many other columns... ║
╠══════════╬═════╬══════╬════════════...
- 33
12
votes
2
answers
12k
views
Does mysql use B-tree,B+tree or both?
I did some search on the matter and I found out that Mysql uses B+Tree index, but when I run "show index" the index type that I get is Btree. And I found in this article that Mysql uses both Btree and ...
- 123
0
votes
1
answer
2k
views
postgres 9.6 - jsonb & indexing - poor performances
On a table (used by a django model) I'm using jsonb column data to store arbitrary data fetched from a webservice:
abs=# \d data_importer_rawdata;
Table "...
- 101
1
vote
1
answer
87
views
How can we foresee (and configure) B-Tree and R-Tree indexes width and depth in PostgreSQL? [closed]
The B-Tree and the R-Tree are two similar index structures that PostgreSQL offers in its implementation.
Both structures can have at most m children per node and as other tree structures, children ...
- 517
2
votes
0
answers
518
views
Sequential scans instead of index with a PostgreSQL conditional index
I have the following PostgreSQL table, in it I store millions of rows.
I'm effectively trying to use it as a work queue, large lumps of JSON go in (status=queued) and get processed (status=processed)....
- 121
2
votes
1
answer
922
views
PostgreSQL covering index on large table as alternative to CLUSTER command
I'm looking for an alternative to executing the CLUSTER command on large tables to keep data efficiently organized on disk, since it requires an ACCESS EXCLUSIVE lock on tables being clustered, making ...
5
votes
4
answers
1k
views
How many B-tree indexes do I need to support lookups by any subset of n columns?
First, some background ideas
Generally, an SQL database which supports multi-column B-tree indexes also supports doing a lookup by a subset of the columns in the index if and only if they're the ...
- 1,085
2
votes
1
answer
603
views
Postgresql extension pageinspect - mean bt_metap
I am using Postgresql extension pageinspect.
Could someone tell me the meaning of these columns: magic, version, root, level, fastroot, fastlevel of the bt_metap function.
This information is not ...
- 201
0
votes
1
answer
304
views
Can you use multiple types of indexes in one composite index
I've built a covering index for a pretty big query which has already halved the select time.
Now, all the columns are just INT(11)'s so there isn't a problem there but one of the columns is a VARCHAR(...
- 294
2
votes
1
answer
105
views
Query results not as expected - Jsonb Postgres
We've created the following table:
CREATE TABLE public.influencers
(
id integer NOT NULL DEFAULT nextval('influencers_id_seq'::regclass),
location jsonb,
gender text COLLATE pg_catalog."...
- 205
5
votes
1
answer
6k
views
Best index for jsonb in Postgres
We have a table containing around 500k rows. The database table is supposed to grow to million of records.
This is how the table looks like:
CREATE TABLE public.influencers
(
id integer NOT NULL ...
- 205
1
vote
0
answers
50
views
Measuring 'data items accessed' by index technique to retrieve item (PostgreSQL)?
In the example I have attached, a btree is being used to search for the number 19. With PostgreSQL execution plan, buffers read/hit are being shown. Which would they be in the example I have attached? ...
- 233
5
votes
1
answer
5k
views
What would be the maximum number of records that can be indexed with a three levels B-tree ? B+ tree?
I am learning dynamic tree-structure organizations and how to design databases.
Consider a DBMS with the following characteristics :
file pages with size 2048 bytes
pointers of 12 bytes
page header ...
11
votes
1
answer
1k
views
How to enter records with keys to an initially empty B+ tree?
Show the result of entering the records with keys in the order (1, 2,
3, 4, 5) to an initially empty B+ –tree of order m = 3. In case of overflow, split the node and do not re-distribute keys to ...
0
votes
1
answer
200
views
Multi-column btree index & INLJ
I have three tables:
FILM(ID,TITLE)
ACTOR(ID,NAME,GENDER)
CAST(ACTOR_ID,FILM_ID,ROLE)
Foreign keys: ACTOR_ID, FILM_ID
And I have created a btree on columns (ACTOR_ID,FILM_ID) of CAST table.
Could ...
- 189
2
votes
2
answers
1k
views
MySQL - Optimal indexing for a lookup table. HASH index, BTREE index or composite PK?
Let's say I have a very large lookup table that looks like this:
CREATE TABLE `MyLookup` (
`FKToTableA` bigint(20) NOT NULL,
`FKToTableB` bigint(20) NOT NULL,
`Count` bigint(20) ...
- 149
0
votes
2
answers
282
views
Creating Compound Indexes on Many Flags
So, according to this article, low-cardinality indexes may negatively impact performance:
http://www.ibm.com/developerworks/data/library/techarticle/dm-1309cardinal/
Let's say you have 15-20 yes/no ...
- 235
1
vote
1
answer
209
views
XML database for linux
I want to be able to store multiple xml objects in a database. But I don't want to just serialize the object and dump it out. Rather I would like to be able to access the database representation of ...
- 113