Buffer caching method and apparatus for the same in which buffer with suitable size is used

A buffer cache apparatus comprising:

• a storage unit storing data;
• a buffer cache storing a balanced tree and free lists, wherein buffers containing data are hierarchically provided as nodes in said balanced tree, and said free lists are respectively provided for different sizes, each of said free lists including at least one free buffer when said at least one free buffer exists;
• and
• a control unit responsive to a data request, wherein said control unit searches said free lists for a desired buffer based on a size of a requested data requested by said data request, when said requested data does not exist in said balanced tree, and adds said desired buffer to said balanced tree to store said requested data from said storage unit into said desired buffer, wherein said desired buffer is the smallest buffer in said free lists having a size larger than or equal to said requested data size;
• wherein each of said free lists comprises a head section indicating said size and said at least one free buffer connected to said head section, when said at least one free buffer exists, and
• wherein said control unit:
• (a) searches said head sections of said free lists based on said requested data size to find one of said free lists which is provided for the smallest one of said sizes larger than said requested data size,
• (b) determines whether said found free list contains said at least one free buffer,
• (c) sets another of said free lists for the next smallest size as said found free list, when it is determined that said found free list does not contain said at least one free buffer, and
• (d) sets as said desired buffer, a free buffer contained in said found free list, when it is determined that said found free list contains said at least one free buffer, from the searching operation or repetition of the setting operation.

A buffer cache apparatus comprising:

• a storage unit storing data;
• a buffer cache storing a balanced tree and free lists, wherein buffers containing data are hierarchically provided as nodes in said balanced tree, and said free lists are respectively provided for different sizes, each of said free lists including at least one free buffer when said at least one free buffer exists;
• and
• a control unit responsive to a data request, wherein said control unit searches said free lists for a desired buffer based on a size of a requested data requested by said data request, when said requested data does not exist in said balanced tree, and adds said desired buffer to said balanced tree to store said requested data from said storage unit into said desired buffer, wherein said desired buffer is the smallest buffer in said free lists having a size larger than or equal to said requested data size, and wherein said control unit releases and deletes one of said data containing buffers from said balanced tree, when at least a part of said requested data exists in said data containing buffer of said balanced tree, and searches said free lists for said desired buffer based on said requested data size.

A buffer cache apparatus comprising:

• a storage unit storing data;
• a buffer cache storing a balanced tree and free lists, wherein buffers containing data are hierarchically provided as nodes in said balanced tree, and said free lists are respectively provided for different sizes, each of said free lists including at least one free buffer when said at least one free buffer exists;
• and
• a control unit responsive to a data request, wherein said control unit searches said free lists for a desired buffer based on a size of a requested data requested by said data request, when said requested data does not exist in said balanced tree, and adds said desired buffer to said balanced tree to store said requested data from said storage unit into said desired buffer, wherein said desired buffer is the smallest buffer in said free lists having a size larger than or equal to said requested data size, and wherein said control unit releases and deletes ones of said data containing buffers from said balanced tree, when at least a part of said requested data exists in said data containing buffers of said balanced tree, and searches said free lists for said desired buffer based on said requested data size.

A buffer cache apparatus comprising:

• a storage unit storing data;
• a buffer cache storing a balanced tree and free lists, wherein buffers containing data are hierarchically provided as nodes in said balanced tree, and said free lists are respectively provided for different sizes, each of said free lists including at least one free buffer when said at least one free buffer exists;
• and
• a control unit responsive to a data request, wherein said control unit searches said free lists for a desired buffer based on a size of a requested data requested by said data request, when said requested data does not exist in said balanced tree, and adds said desired buffer to said balanced tree to store said requested data from said storage unit into said desired buffer, wherein said desired buffer is the smallest buffer in said free lists having a size larger than or equal to said requested data size, and wherein said control unit corrects said balanced tree such that depths from a root node to leaf nodes in said nodes of the balanced tree are as uniform as possible.

A buffer caching method comprising:

• determining whether a requested data specified by a data request exists in a balanced binary tree, wherein buffers are hierarchically provided as nodes in said balanced binary tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced binary tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced binary tree;
• and
• storing said requested data from said storage unit into said desired buffer.

A buffer caching method comprising:

• determining whether a requested data specified by a data request exists in a balanced tree, wherein buffers are hierarchically provided as nodes in said balanced tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced tree;
• and
• storing said requested data from said storage unit into said desired buffer,
• wherein said searching includes:
• (a) finding one of a plurality of free lists based on said requested data size, wherein said found free list is provided for the smallest one of said sizes larger than said requested data size;
• (b) determining whether said found free list contains said at least one free buffer;
• (c) setting another of said free lists for the next smallest size as said found free list, when it is determined that said found free list does not contain said at least one free buffer;
• and
• (d) setting as said desired buffer, a free buffer contained in said found free list, when it is determined that said found free list contains said at least one free buffer, after the finding operation (a) or repetition of the setting operation (c).

A buffer caching method comprising:

• determining whether a requested data specified by a data request exists in a balanced tree, wherein buffers are hierarchically provided as nodes in said balanced tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced tree;
• storing said requested data from said storage unit into said desired buffer;
• releasing and deleting one of said data containing buffers from said balanced tree, when said requested data exists in said data containing buffers of said balanced tree;
• and
• searching free lists for said desired buffer based on said requested data size.

A buffer caching method comprising:

• determining whether a requested data specified by a data request exists in a balanced tree, wherein buffers are hierarchically provided as nodes in said balanced tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced tree;
• storing said requested data from said storage unit into said desired buffer;
• releasing and deleting data containing buffers from said balanced tree, when said requested data exists in said data containing buffers of said balanced tree;
• and
• searching free lists for said desired buffer based on said requested data size.

A buffer caching method comprising:

• determining whether a requested data specified by a data request exists in a balanced tree, wherein buffers are hierarchically provided as nodes in said balanced tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced tree;
• storing said requested data from said storage unit into said desired buffer;
• and
• correcting said balanced tree such that depths from a root node to leaf nodes in said nodes of the balanced tree are as uniform as possible.

A recording medium storing a program for executing a buffer caching method which comprises:

• determining whether a requested data specified by a data request exists in a balanced binary tree, wherein buffers are hierarchically provided as nodes in said balanced binary tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced binary tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced binary tree;
• and
• storing said requested data from said storage unit into said desired buffer.

A recording medium storing a program for executing a buffer caching method which comprises:

• determining whether a requested data specified by a data request exists in a balanced tree, wherein buffers are hierarchically provided as nodes in said balanced tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced tree;
• and
• storing said requested data from said storage unit into said desired buffer;
• wherein said searching includes:
• (a) finding one of plurality of free lists based on said requested data size, wherein said found free list is provided for the smallest one of said sizes larger than said requested data size;
• (b) determining whether said found free list contains said at least one free buffer;
• (c) setting another of said free lists for the next smallest size as said found free list, when it is determined that said found free list does not contain said at least one free buffer;
• and
• (d) setting as said desired buffer, a free buffer contained in said found free list when, it is determined that said found free list contains said at least one free buffer, after the finding operation (a) or repetition of the setting operation (c).

A recording medium storing a program for executing a buffer caching method which comprises:

• determining whether a requested data specified by a data request exists in a balanced tree, wherein buffers are hierarchically provided as nodes in said balanced tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced tree;
• storing said requested data from said storage unit into said desired buffer;
• releasing and deleting one of said data containing buffers from said balanced tree, when said requested data exists in said data containing buffers of said balanced tree;
• and
• searching free lists for said desired buffer based on said requested data size.

A recording medium storing a program for executing a buffer caching method which comprises:

• determining whether a requested data specified by a data request exists in a balanced tree, wherein buffers are hierarchically provided as nodes in said balanced tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced tree;
• storing said requested data from said storage unit into said desired buffer;
• releasing and deleting data containing buffers from said balanced tree, when said requested data exists in said data containing buffers of said balanced tree;
• and
• searching free lists for said desired buffer based on said requested data size.

A recording medium storing a program for executing a buffer caching method which comprises:

• determining whether a requested data specified by a data request exists in a balanced tree, wherein buffers are hierarchically provided as nodes in said balanced tree;
• searching a desired buffer from free buffers with different sizes based on a size of said requested data when it is determined that said requested data does not exist in said balanced tree, said desired buffer is the smallest free buffer having a size larger than or equal to said requested data size;
• adding said desired buffer to said balanced tree;
• storing said requested data from said storage unit into said desired buffer;
• and
• correcting said balanced tree such that depths from a root node to leaf nodes in said nodes of the balanced tree are as uniform as possible.