( Midpoint insertion

Info Catalog ( Multiple key caches ( MyISAM key cache ( Index preloading Midpoint Insertion Strategy
 By default, the key cache management system of MySQL 4.1 uses the LRU
 strategy for choosing key cache blocks to be evicted, but it also
 supports a more sophisticated method called the "midpoint insertion
 When using the midpoint insertion strategy, the LRU chain is divided
 into two parts: a hot sub-chain and a warm sub-chain. The division
 point between two parts is not fixed, but the key cache management
 system takes care that the warm part is not "too short," always
 containing at least `key_cache_division_limit' percent of the key cache
 blocks.  `key_cache_division_limit' is a component of structured key
 cache variables, so its value is a parameter that can be set per cache.
 When an index block is read from a table into the key cache, it is
 placed at the end of the warm sub-chain. After a certain number of hits
 (accesses of the block), it is promoted to the hot sub-chain.  At
 present, the number of hits required to promote a block (3) is the same
 for all index blocks.  In the future, we will allow the hit count to
 depend on the B-tree level of the node corresponding to an index block:
 Fewer hits will be required for promotion of an index block if it
 contains a non-leaf node from the upper levels of the index B-tree than
 if it contains a leaf node.
 A block promoted into the hot sub-chain is placed at the end of the
 chain.  The block then circulates within this sub-chain. If the block
 stays at the beginning of the sub-chain for a long enough time, it is
 demoted to the warm chain. This time is determined by the value of the
 `key_cache_age_threshold' component of the key cache.
 The threshold value prescribes that, for a key cache containing N
 blocks, the block at the beginning of the hot sub-chain not accessed
 within the last `N*key_cache_age_threshold/100' hits is to be moved to
 the beginning of the warm sub-chain. It then becomes the first
 candidate for eviction, because blocks for replacement always are taken
 from the beginning of the warm sub-chain.
 The midpoint insertion strategy allows you to keep more-valued blocks
 always in the cache. If you prefer to use the plain LRU strategy, leave
 the `key_cache_division_limit' value set to its default of 100.
 The midpoint insertion strategy helps to improve performance when
 execution of a query that requires an index scan effectively pushes out
 of the cache all the index blocks corresponding to valuable high-level
 B-tree nodes. To avoid this, you must use a midpoint insertion strategy
 with the `key_cache_division_limit' set to much less than 100.  Then
 valuable frequently hit nodes will be preserved in the hot sub-chain
 during an index scan operation as well.
Info Catalog ( Multiple key caches ( MyISAM key cache ( Index preloading
automatically generated byinfo2html