Skip to main content

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
63 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....
Tomas F.'s user avatar
  • 123
1 vote
5 answers
201 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 ...
mediocre's user avatar
  • 129
0 votes
1 answer
42 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); ...
Ali Azimi's user avatar
0 votes
1 answer
53 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]&...
Macchiatow's user avatar
1 vote
1 answer
203 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 ...
Anvil's user avatar
  • 11
1 vote
1 answer
139 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 ...
obanadingyo's user avatar
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 ...
Ilya's user avatar
  • 1
2 votes
2 answers
393 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) ...
nick314's user avatar
  • 147
0 votes
0 answers
69 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 (...
GenGG's user avatar
  • 15
8 votes
2 answers
988 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 ...
John's user avatar
  • 765
0 votes
1 answer
188 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 ...
GenGG's user avatar
  • 15
1 vote
2 answers
64 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 ...
GenGG's user avatar
  • 15
1 vote
1 answer
233 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 ...
g4s8's user avatar
  • 111
0 votes
1 answer
99 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 ...
ide's user avatar
  • 101
0 votes
0 answers
60 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 ...
user5721565's user avatar
0 votes
1 answer
639 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 ...
Albert's user avatar
  • 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, ...
HelloMachine's user avatar
0 votes
0 answers
257 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"...
Rebooting's user avatar
  • 109
0 votes
2 answers
409 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 ...
svenema's user avatar
  • 151
0 votes
1 answer
129 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 ...
Steven L.'s user avatar
  • 165
4 votes
2 answers
474 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 ...
J.D.'s user avatar
  • 38k
1 vote
1 answer
595 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 ...
J.D.'s user avatar
  • 38k
-1 votes
1 answer
150 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 ...
xing Zì's user avatar
  • 101
0 votes
1 answer
3k 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, ...
collimarco's user avatar
1 vote
0 answers
298 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 ...
Paul Draper's user avatar
0 votes
2 answers
401 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 ...
Marcus's user avatar
  • 378
4 votes
1 answer
955 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 ...
Optic_Ray's user avatar
3 votes
2 answers
3k views

Containment check tstzrange @> timestamptz not using btree or gist index

Schema: Column | Type ----------------------+-------------------------- id | integer event_id | integer ...
Gajus's user avatar
  • 1,195
1 vote
2 answers
2k 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 ...
Dinesh Kumar's user avatar
-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 (...
Rodolfo Salazar's user avatar
18 votes
3 answers
14k 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 ...
Sampson Crowley's user avatar
3 votes
1 answer
922 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... ║ ╠══════════╬═════╬══════╬════════════...
Alex's user avatar
  • 33
11 votes
2 answers
11k 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 ...
Noussa Smiley's user avatar
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 "...
Luke's user avatar
  • 101
1 vote
1 answer
83 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 ...
Zeruno's user avatar
  • 497
2 votes
0 answers
512 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)....
Andy Smith's user avatar
2 votes
1 answer
897 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 ...
Thomas C. G. de Vilhena's user avatar
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 ...
Mark Amery's user avatar
  • 1,085
2 votes
1 answer
593 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 ...
Neto's user avatar
  • 201
0 votes
1 answer
293 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(...
Florian Humblot's user avatar
2 votes
1 answer
99 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."...
borjagvo's user avatar
  • 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 ...
borjagvo's user avatar
  • 205
1 vote
0 answers
49 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? ...
audlift-bit's user avatar
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 ...
Revolucion for Monica's user avatar
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 ...
Revolucion for Monica's user avatar
0 votes
1 answer
198 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 ...
Moras's user avatar
  • 179
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) ...
mBrice1024's user avatar
0 votes
2 answers
277 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 ...
Dan's user avatar
  • 235
1 vote
1 answer
207 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 ...
dpetican's user avatar
  • 113
1 vote
2 answers
398 views

Clustered Index Misunderstanding

I've read in couple of articles that clustered index is as the same as table, or if you read using clustered index, you have the whole record. Some say, clustered index stores the whole records in ...
user avatar