On 26Jun2019 11:01, Mats Wichmann <m...@wichmann.us> wrote:
On 6/26/19 4:40 AM, mhysnm1...@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 <c...@cskk.id.au>
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
