Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How does database indexing work? (2008)

stackoverflow.com

Post reply on HN
Print view View original

31–40 of 62 posts

Re: How does database indexing work? (2008)

#31

Post by broken8ball »

getcrunk wrote: post #28
masklinn wrote: post #20

Earlier quoted context omitted.

> A btree is a kind of binary tree By definition a binary tree means there are two children per node. Binary is the one thing a b-tree is not .

Uhh. A b tree is a self balancing binary (search) tree.

Binary implies two. Both B-trees and BSTs exist in the universe of m-ary trees. A BST and a B-tree would be equivalent only if the branching factor of the B-tree was set to 2, but practically this is rarely the case with indexes, given that a higher branching factor is generally more favorable to lookup times (“block accesses”) since the hight of the B-tree is reduced as m increases.

Re: How does database indexing work? (2008)

#32

Post by quelltext »

So how does a binary search work when the disk blocks are essentially a linked list as the top answer initially says? They just assume that it's possible to jump through a contiguous array of blocks for their later analysis but initially state blocks aren't necessary contiguous.

Re: How does database indexing work? (2008)

#33

Post by bogomipz »

eatonphil wrote: post #18

If you want to see a dumb example of how you can implement indexing on top of a SQL database without it, I wrote a tutorial on implementing basic indexes [0] as part of a series on making a SQL database from scratch. And of course, Use the Index Luke is a great reference for the real world. [0] https://notes.eatonphil.com/database-basics-indexes.html [1] https://use-the-index-luke.com/

I loved your series on writing a SQL DB from scratch. I also enjoyed your recent SMTP post as well. I hope you continue to do these, they're always good reading.

Re: How does database indexing work? (2008)

#34

Post by jameshart »

quelltext wrote: post #32

So how does a binary search work when the disk blocks are essentially a linked list as the top answer initially says? They just assume that it's possible to jump through a contiguous array of blocks for their later analysis but initially state blocks aren't necessary contiguous.

Their point is that in order to get log(n) access speed you need a sorted random access list, not that if you sort the items in a linked block list you can use binary search on it. They go on to explain how a database index constructs such a thing over the linked block list.

Re: How does database indexing work? (2008)

#35

Post by westurner »

https://en.wikipedia.org/wiki/Database_index

https://en.wikipedia-on-ipfs.org/wiki/Database_index

From "Hosting SQLite Databases on GitHub Pages" https://news.ycombinator.com/item?id=28021766 re: edgesearch, HTTP/3 QUIC UDP, :

> Serverless full-text search with Cloudflare Workers, WebAssembly, and Roaring Bitmaps https://github.com/wilsonzlin/edgesearch

>> How it works: Edgesearch builds a reverse index by mapping terms to a compressed bit set (using Roaring Bitmaps) of IDs of documents containing the term, and creates a custom worker script and data to upload to Cloudflare Workers

Re: How does database indexing work? (2008)

#36

Post by dvirsky »

quelltext wrote: post #32

So how does a binary search work when the disk blocks are essentially a linked list as the top answer initially says? They just assume that it's possible to jump through a contiguous array of blocks for their later analysis but initially state blocks aren't necessary contiguous.

That's why disk indexes usually use B-trees.

Re: How does database indexing work? (2008)

#37

Post by masklinn »

broken8ball wrote: post #31
getcrunk wrote: post #28

Earlier quoted context omitted.

Uhh. A b tree is a self balancing binary (search) tree.

Binary implies two. Both B-trees and BSTs exist in the universe of m-ary trees. A BST and a B-tree would be equivalent only if the branching factor of the B-tree was set to 2, but practically this is rarely the case with indexes, given that a higher branching factor is generally more favorable to lookup times (“block accesses”) since the hight of the B-tree is reduced as m increases.

> practically this is rarely the case with indexes

Seems like it would be extremely odd to have a 2-2 btree, you’d just get a significantly more complicated BST no?

I’d figure you’d want to fill a cacheline with something typical-ish, so probably at least 4 (this way if you have 4 children and 3 keys, the keys are 8 bytes and the child links are straight pointers your node is 56 bytes and you can add some metadata e.g. a bitmap).

Apparently Rust’s BTreeMap is a 6-11 btree but I don’t know how they picked the branching factor.

Re: How does database indexing work? (2008)

#38

Post by xtracto »

didip wrote: post #24

You know what I would like to see (for learning)? A simplified project how indices, for example in b-tree, are stored in segment files.

This. I was hopeful that the linked article would explain how b-trees are practically used for indexes in DB engines. I already know what a db index is (databases 101 software eng) and why are they used, but would love a clear explanation of how are they implemented

Re: How does database indexing work? (2008)

#40

Post by btilly »

xtracto wrote: post #38
didip wrote: post #24

You know what I would like to see (for learning)? A simplified project how indices, for example in b-tree, are stored in segment files.

This. I was hopeful that the linked article would explain how b-trees are practically used for indexes in DB engines. I already know what a db index is (databases 101 software eng) and why are they used, but would love a clear explanation of how are they implemented

https://perl.plover.com/BTree/article.html is an introductory article about how a b-tree is implemented. It has example code for it in Perl.

It doesn't actually match low level implementations for a number of reasons. Such as the need to fix the page size the block fits in rather than the count of things in the block, and locking for concurrent access. But the data structure itself still looks the same.

Post reply on HN