JL Computer Consultancy
What are Hash Chains.
(Recreated from an original written for the Dizwell Wiki). |
June 2006 |
As a starting point for this page, here’s a short list of questions that I recently received about “cache buffers chains”, and the (quick) answers that I gave.
- What is a hash chain? Is it an array?
No, for the cache buffers chains it is a doubly linked list
- Are hash chain and hash list two different names for the same thing or is hash list just another way of saying linked list?
The terms are two names for the same things - also called hash buckets.
- What is a linked list? Is this a separate structure that contains the DBA of the next and the previous buffer headers on that list?
A linked list is a collection of memory chunks where each chunk contains a pointer to the next chunk. If there are two pointers in each chunk (one “forwards” one “backwards”) you have a doubly linked list.
- When we say that block headers are placed on a doubly-linked list, why the list has to be doubly linked?
If you arrange items into a doubly-linked list, you can remove an item from the list very easily. You follow the two pointers from the current item to the two adjacent items, and change their “backward” pointers so that they point to each other rather than pointing to the item you are removing.
- I would appreciate any help.
Draw a picture of about 5 rectangles connected in a chain by pairs of arrows and re-read the above.
- Follow-up question: so, the hash chain/list/bucket is a doubly-linked list and the buffer headers are placed on this list and not on any other structure?
Buffers headers are placed on these lists. There are many separate lists of this specific type No buffer header goes on to more than one such list Each list has a known starting point. Many starting points (typicall 64 – 128) are covered by each cache buffers chains latch
But there are other types of linked list that also run through the collection of buffer headers, such as the LRU (least recently used) chains and the checkpoint chains.
- Is it this list that processes traverse sequentially after the hash function is applied and the hash chain is determined.
Correct. To check if a block is in memory, the process computes a hash value based (I think) on the block address, type and tablespace - and this tells it which hash chain to traverse
