B-Trees on Disk (Database internals) 

Same for me

B(+)-Tree is a data structure which is designed to store data on the disk. In memory you can have a binary search tree or a b-tree. To visualise, lets see if the following helps? - In memory each node can have : Intermediate - a list of pointers to children - some keys used to guide the search algorithm for CRUD. (show me where to go next?) Leaf: - ordered list of key,value pairs - key is the search column - value is a pointer for actual value OR an actual value (depends on implementation). - On disk: - All of these are files, that are stored on blocks. - Each block has a list of entries, which can either represent an internal node OR a leaf node. - A pointer to another node can be replaced with a record_id (page_id, file offset). - Leaf node is a block that contains key,value pairs in order so you can search for a specific key once you read a block from the disk. - again value can be a record_id (ex. Postgres) OR the data itself (ex. MySQL). So basically, each in memory node represents a block on disk which has an ordered list of keys and|or pointers (record_id) to another blocks (children pointers). So when you read a block, you match the key and decide which block to load next. Now a block can be filled completely OR be half filled based on the how your data is distributed. But you can imagine, because of the data layout (as a B+-Tree) on the disk, the number of blocks you need to read from the disk is log(N) base B, where N is the total number of keys in the dataset and B is the number of keys in one block (node). Does this help? Please let me know if it doesn't, if I try to simplify further.

@@TheGeekNarrator This helps, thanks ! But I am stuck at visualizing how the in-memory pointers to nodes (be it top-down traversal or left-right traversal) get persisted into disk. Pointers are relevant in context of memory only. I think, you are saying the pointers get translated to block address at the time of persistence? If yes, then the question is: who does this translation and how? I thought, the block addresses are known deep at OS/Disk Driver/HDD level?

I am not sure I understand. Are you talking about replacing the usage of B-Trees with arrays? Or just the leaf nodes as arrays? I am not sure how using the array index would work on the disk. Could you please elaborate with an example?

​@@TheGeekNarrator Sure. Sorry for that. I was making a point that we can replace the leaf node as arrays. Use-case : Given a key, find the pageId, tupleId. For simplicity, let's consider the key as an integer. We are using B-Tree for storing indices. This B-Tree node itself will also be stored on the disk. Let's assume each node corresponds to a block on the disk. For CPU to process anything, it had to bring the information from disk to memory and process it. That said, the data on the disk corresponding to the root node will be put in memory, B-Tree node will be constructed and the execution begins. We scan the B-tree node, look at the key and depending on the key, move to the corresponding pointer. We continue this process until we reach the leaf node. In the leaf node, we will probably be storing k1 : p1, t1, k2:p2, t2, etc... Now, the curiosity is : storing keys on the root node / intermediate is required to figure out which path to traverse. On the leaf node, do we need to store these keys? In my opinion it's not required and we can leverage the computes internal representation of memory allocation to get the value for a given key. Let's say a leaf node is holding 256 keys that has a pageId and tupleId. In B-Tree node, we need to store these 256 keys in it which consumes space. If we use arrays as the leaf node, since anyways we have to construct the data structure in memory before we process it, if we construct it as an array, memory will be allocated sequentially (say 100 - 356). For getting the key 1 -> we can go to 100th memory address, fetch the value. for key 2 -> go to 101st memory address and fetch the value. On a side note, If my understanding is correct, for any data structure that requires say 1000 bytes, computers will allocate memory sequentially only. In such a case, we can just piggyback on the memory representation to figure out the indices. Because indices are also sequential.

Yes - I have planned a few more in this series. As soon as the time permits they will be published. Thanks

In which data structure?