[Tutor] data structures general query

[Cameron Simpson]

On 26Jun2019 11:01, Mats Wichmann <mats at wichmann.us> wrote:
>On 6/26/19 4:40 AM, mhysnm1964 at gmail.com wrote:
>> Link lists I would guess be useful in an index for a database?
>
>I believe the "classic" use case is memory management - keeping track of
>chunks of memory.

Flipping this, your typical ordered database index (unless the tech has 
advanced further) is a B+ tree possibly with a doubly linked list 
threaded through the leaf nodes.

So a B+ tree is a sorted tree structure which is maintained in a 
balanced way so that the depth is pretty consistent across the tree, in 
turn so that there is not particularly long branch equivalent to have 
particular keys which are very expensive to look up. Unlike a binary 
tree a B+ tree has many keys at each node because this makes for 
efficient storage of the nodes in "blocks", whatever size is useful, and 
is also makes the tree shallower, making lookups cheaper.

The leaf nodes point at the associated records (or possibly just hold 
keys if there are no records), and the doubly linked list of leaf nodes 
means you can traverse forwards or backwards from one leaf to the next 
in either order. Which makes find ranges of keys efficient: "SELECT ...  
WHERE key >= value ORDER BY key DESC" and its many variants.

As has been pointed out by others, the various computer science basic 
structures are often built up into something different or more complex 
depending on what your data access pattern will be.

It is important to understand the basic structures so that you can 
reason about their trade offs, and in turn understand more complex 
related structures. This goes both ways: in design you choose a 
structure to support what you're going to do. In use, you might choose 
to approach a problem differently depending on what data structure is 
used to arrange the data, because some actions are cheap in some 
structures and expensive in others, so you choose the efficient action 
where possible.

Cheers,
Cameron Simpson <cs at cskk.id.au>