#btrees

[davidepalermoblog]

Stasera con @wtf_84 all'incontro "Il Futuro del Nord Ovest" | 150 @la_stampa | Vercelli, i canali digitali Con Maurizio Molinari (Direttore #LaStampa), Luca Ubaldeschi (Vice Direttore Vicario La Stampa), Maura Forte (Sindaca di #Vercelli), Tareq Rajjal (General Manager di #Amazon Italia Logistica) e altri ospiti del territorio. #innovazione #MakeItFruitful #BTREES #èperlavoro #digital #Piedmont (presso Teatro Civico di Vercelli)

[techiemedotin]

Splitting and Merging B Tree Nodes

Splitting and Merging B Tree Nodes

This post is to be read in conjunction with another post Introduction to B Trees. Here we learn that in certain operations the B Tree properties might get disturbed and it will need a fix. Splitting and Merging B Tree Nodes are the only operations which can re-establish the properties of the B Tree.

How does a B Tree get unbalanced?

The tree is not just to read and search data. There are…

View On WordPress

[techiemedotin]

Introduction to B Trees

Introduction to B Trees

This post is just an introduction to B Trees and here we will discuss one of the complicated data structures, B Trees. I would advice the reader to get familiar with the Tree data structures, and Balanced Trees. For e.g. : Binary Search Trees, AVL Trees, Red Black Trees and 2-3-4 Trees.

If you are not familiar with any/few of the above mentioned data structures, then please do not worry, I will…

View On WordPress

[cat-notes-blog]

Indexes and Btrees

Indexes make selection faster, insertions and updates slower. They also take up memory. 

Composite keys are in Dictionary Order. E.g. if we have an index on (A,B), we can search on A but not on B. 

Btrees are NOT binary trees. Each node is a physical page. It's a balanced, height-adjusted tree. 

B+ trees: all the leaves are linked together. This makes sequential access easier. 

We have a parameter called degree, d. 

Each node has between d and 2d keys (except the root). 

No data in internal nodes

The cost comes from disk reads, i.e. hopping from node to node. 

B+Trees in Real Life

Typical order: 100

Typical fill-factor: 67%

Average fanout: 133

Height 4 capacity: 133^4 = 312,900,700 records

Height 3 capacity: 133^3 = 2,352,637 records

Top 3 levels sit in the buffer pool. They sit inside the RAM. 

Insertions into Btrees

If overflow, split node and insert in parent. 

An index is clustered if the data is ordered in the same way as the underlying data. Clustered data is a lot cheaper for range query. 

[lesliebklein]

Thinking REALLY BIG

Type "the" into Google. Google searches 9 billion pages in .29 seconds. How does it do that? Try "chocolate". 197 million pages in .48 seconds. (No wonder we hate when the microwave takes 2 mins to boil water!)

When we search Google, we are searching an index of the data, not the data itself. We need a data structure that can store billions of keys and return a value in response to a query almost instantaneously. The answer: B-Trees.

B-Trees are a self-balancing tree where each node can have many children. If a node stores up to M keys, then it has M + 1 children. Suppose a tree stores 60 billion keys with nodes that store up to 1000 keys. To find a given key, the number of nodes searched  is <= 4. WAT? 

The reason is that the tree is very flat. The number of keys in a node ranges from M/2 to M (except for the root which has 2 keys). In 1979 (hey, B-Trees are not new), a theorist named Yao proved that, for random keys, the amount of empty space is about 44%. In the worse case, the height of the tree is (log base M/2) N. So, for M = 1000 and N = 62 billion, the height is 4.

But how can I search a B-tree with 62 billion keys? I can't fit it in memory. All the programs I write use some data structure that fits into memory and I don't even think about it.

One answer is virtual memory. If your machine has a MMU (Memory Management Unit) then you as a programmer can ignore details about what is in memory and what is on external storage. The MMU maps physical hardware addresses, wherever they are, to addresses that appear to be contiguous, in-memory addresses.

A more basic concept is that the program only needs to bring into memory the chunk of data that it needs to access. It only needs to access the nodes that it hits along the search path of the B-tree. So if the search, starting at the root, takes the left link, then the middle link, then the right link, before it hits a leaf node, then the program only needs to read in the those 3 nodes plus the leaf node. The program then searches for the value associated with the query key in the leaf node.

To explore B-trees and build one of my own, I decided to index the web pages that I can reach from www.princeton.edu  - and to explicitly read and write each of the nodes to/from disk. Each node stores 1000 keys. A key is a word on a web page. The value associated with the key is the set of urls on which the word is found. I limit the number of nodes in the tree to 200. (My goal is to get up to 1000 but first I have to deal with broken links and connection errors.)

As I type this, I can see the program in action. The tree starts as 1 node: the root. When it fills up to 1000, it splits into 2 nodes of 500 keys each (left and right). A new root is created that stores 2 keys: 1 key links to the left node and 1 to the right node. Every time a new root is created the tree height grows by 1.

After a node splits, I write each node to its own file on disk. After a search or insert completes, the only node in memory is the root. All other nodes in the search path are written to disk. When a new search or insert begins, only the files associated with the nodes in the search path are opened. By looking at the directory with the files, I can see them being updated (keys added to it) and new files created (nodes splitting). Watching the tree grow in real time is cool.

In the process of building an index of web pages and then searching for search terms in the index (271 urls from princeton homepage, 31 tree nodes, 20180 unique words, <2 avg node hits for each search - the tree has height = 1!), I learned more python along the way:

used python 3, requests, and BeautifulSoup to scrape the web pages for urls and words. Detours: unicode, Ned Batchelder's pycon video on unicode , json and pickle (and their differences), file modes (text and byte) and what these mean in python 3.

And yeah... using a python IDE is a new world. The ability to stop a program and navigate down a tree by expanding its nodes almost makes debugging fun.

P.S. What does the B mean in B-tree? Nothing. It could stand for 'Bayer' (the inventor of B-trees) or B for 'balanced' multiway trees. But it doesn't.