KR20030044498A - Data Structure, Block Assignment and Record Retrieval Method of Main Memory DataBase Management System - Google Patents

Abstract

The present invention relates to a data structure, a block allocation method, and a record retrieval method of a main memory device database management system which can improve retrieval performance while properly expressing correlation of large data.

The linked list significantly slows down the process because the physical distribution in the storage is scattered and each data has to be sorted on the list, and there is a precondition that queues must be used within a limited size. Since there is a structural deformation overhead that occurs, the conventional main memory database management system has a problem that can not use the existing data structure as it is.

According to the present invention, a basic unit of dynamic allocation is designated as a block, and the address of each block is associated and managed in a hierarchical structure, so that a subset of data can be continuously arranged in block units, and the number of dynamic allocations is increased. It will be reduced by the number of records in the block.

Description

Data Structure, Block Assignment and Record Retrieval Method of Main Memory Database Management System}

The present invention relates to a data structure of a main memory database management system, a block allocation method, and a record retrieval method. In particular, the present invention relates to a data structure of a main memory database management system that can improve retrieval performance while properly expressing a correlation between large amounts of data. Block allocation and record retrieval methods.

In general, in an application such as a database management system (DBMS), the number of records belonging to a relation is theoretically an infinite concept. That is, there is a possibility that the number of records increases indefinitely as time changes.

Therefore, in a conventional database management system, a large amount of data is stored in a large auxiliary storage device (hard disk, tape, etc.) in the form of a file, and loaded into the main memory using a caching technique when necessary in an application. And swapping.

However, in the main memory database management system (Main Memory DBMS), which has high real-time performance and performance, the process must be performed while resident large data is stored in the main memory device. As individual data is the basic unit of allocation, the data is dynamically allocated as much as the size of individual data and the data structures are connected.

As described above, when dynamically allocating associated data in one process, the data structure indicating the relevance (post-relationship, dependency relationship, etc.) of the data includes a linked list, a tree structure, and a queue. (Queue).

While the linked list described above is a linked (non-sequential) representation of the ordered list, it is easy to insert or delete an element at an arbitrary position, while for each element, additional information about the position of the next element in the link (pointer variable) is added. Since it needs to be stored, it requires additional storage space for pointers, and there are simple linked lists, circular linked lists, dual linked lists, double circular linked lists, and the like.

When inserting new data using the linked list, copy the data value to the assigned address, and then indicate the order or association with the existing data with the pointer (link) for linking. Depending on the type, you must connect all of the circular pointers before, after, and after.

When deleting data, search for the data to be deleted and delete the node, modify the link of the preceding node with the pointer of the trailing node pointed to by the deleting node, idle the deleted node, and move the deleted node according to the type of the connection list. The trailing nodes must be connected in the proper way.

On the other hand, a queue is a special form of an sequential list, in which the insertion of an element is done in the rear, the deletion is in the front, and the first-in, first-out (FIFO) list prints the first element first. do.

There are two types of queues: a moving queue and a circular queue. A moving queue is a queue that operates by inputting the entire contents of the queue when the rear reaches one end of the queue and the other end is empty. The queue moves to prevent overflow. And circular cue is the most powerful cue representation, and considers the primary array as circular, and inserts directly into useful space by changing only the rear value when there is useful space. It is a circular structure that connects both sides by changing from n) to Q (0: n-1).

As such, the cue performs the insertion / deletion process using indicators in the queue called rear (the last pointer) and front (the first printer). Increment, and delete one by one the front. And since circular queues can't represent empty and overflow states when using only the front and the front, the tag is zero if the back and the front are the same using the tag variable. For overflow, set the tag to 1.

On the other hand, the tree is a kind of connected non-purified graph, which has a root node as a finite set of one or more nodes, and the remaining nodes have a property of being separated into a separate set.

As such types of trees, an order tree (a tree in which the positions of left and right arrays of nodes of the same level are fixed so that the positional meaning is important) (a> b) and an unordered tree {a tree whose positional meaning is not important (a = b)}. Another classification is to classify similar trees (trees with the same structure, such as the number and position of the nodes in the tree, but with different data parts of the nodes) into equivalent trees (trees with the same data in the same location as well as the structure of the tree). It may be.

As mentioned above, the tree data structure is very diverse. Looking only at the insertion / deletion and transformation operations of the tree structure, which are common to all trees, when inserting, the position of the node to be inserted is selected according to the characteristics of the tree structure. Search and insert data at that location. Then, connect the rest of the data structure of the tree structure, that is, the connection pointer with other nodes, to match the tree structure. At this time, when a node overflow occurs, the overhead of changing the structure of the entire tree occurs.

When deleting, the node to be deleted is searched for and the data is deleted. When an underflow of the node occurs, an overhead of changing the entire tree structure occurs.

In the above, we looked at the data structure indicating the relevance of data when dynamically allocating the associated data in one process. When storing a large amount of data using a linked list, the physical distribution in the storage device is distracted, This slows down the process significantly because each piece of data must be sorted on the list.

In addition, there is a precondition that queues should be used within a limited size. Although overflow / underflow solutions exist, it is impossible for a writer to know the infinite data size in a program, so the theoretically large capacity increases indefinitely. Not available for data.

The tree structure is the most appropriate data structure to use for large data. However, due to the nature of the tree structure, there is a rebalancing overhead that occurs when inserting and deleting. In the skewed state, the performance is improved. It has the disadvantage of significantly deteriorating.

Therefore, in a main memory device database management system requiring real-time speed, the process must proceed while resident a large amount of data in the main memory device, and thus there is a problem that the existing data structure cannot be used as it is.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-described problem, and by designating a basic unit of dynamic allocation as a block and associating and managing addresses of each block in a hierarchical structure, a process can be performed while resident a large amount of data in a main memory device. The purpose of the present invention is to provide a data structure, a block allocation method and a record retrieval method of a main memory device database management system.

1 and 2 show the data structure of the main memory device database management system according to the present invention;

3 is a flowchart for explaining a block allocation method of a main memory device database management system according to the present invention;

4 is a flowchart for explaining a record retrieval method of the main memory device database management system according to the present invention;

The data structure of the main memory device database management system according to the present invention for achieving the above object, designates the basic unit of dynamic allocation as a block, and associates the addresses of the blocks using a hierarchical structure called level, The upper level consists of an exponential structure that contains all the data of the lower levels.

In this case, the size of the block is determined according to how many records are contained in one block.

The blocks may include: a pointer which becomes a reference indicating the corresponding block when searching; Level information for each level; With the current highest level; The number of records in one block; And based on block information including one record size.

The level information may include: the number of empty blocks in one level node; The maximum number of records included in one level; It is characterized by including the address of the block last allocated in the level.

On the other hand, in the block allocation method of the main memory device database management system according to the present invention, the level information is checked from a low level to search for a level in which an empty block exists, determine the number of records to be stored in the block, and allocate the block. Then assigning an address of the allocated block to a variable called root; If the assigned level does not exist according to the existence of the assigned level, allocating a new level; Increasing the level when the level is increased according to whether the level is increased when there is an assigned level; If the level is not increased, the process of designating the address of the last allocated block in the last allocated block at the lower level of the current level as N multiplied by 4 bytes and the address of the allocated block; ; Setting an association relationship between the current level and the lower level when the lower level exists according to the existence of the lower level; If the lower level does not exist, the process includes designating the last block address of the lower level as the address of the allocated block.

Here, the process of newly assigning the level may include setting the level of block information to 1, assigning a pointer to a value assigned to the variable named root, and assigning the last block address of the level information of level 1 to the variable named root. Characterized in that the process of specifying the assigned value.

In the process of increasing the level, the level of block information is increased by one, the number of empty blocks included in the increased level is set to N-1, and a preset pointer that indicates the allocated block is set. Assigning the root value of the block; Designating an address of the allocated block as an address of a block used at a current level, and designating an address of the allocated block as a root of a block indicated by the allocated block; And a process of designating the address of the last allocated block in the last allocated block at the current level as N plus 4 bytes plus the address of the allocated block.

The establishing of the association may include assigning a last block address of a lower level as an address of a block allocated last from a higher level of the lower level, and assigning an address of an allocated block to N in the allocated block. Assigning a value obtained by multiplying 4 bytes to an address of the allocated block and repeatedly setting the number of empty blocks included in the lower level to N-1 to a lower level higher level; And assigning the last block address of the lowest level to the address of the block allocated last from the upper level of the lowest level.

On the other hand, the record retrieval method of the main memory device database management system according to the present invention, the top level of the block that is the index of the operation of dividing the index of the record to be searched by the maximum number of records that can be included in the lower level of the highest level Searching in; Retrieving a process of substituting the remainder of the operation into the index and searching for the block having the index of the quotient of the operation obtained by dividing the index by the maximum number of records that can be included in the next lower level of the lower level. Repeatedly performing the steps down to a lower level until a block in which a desired record exists is found; And finally calculating the address of the search record based on the value assigned to the index, the record size, and the address of the last searched block.

Hereinafter, a data structure, a block allocation method, and a record retrieval method of a main memory device database management system according to an exemplary embodiment of the present invention will be described in detail with reference to the accompanying drawings.

1 and 2 are roads showing the data structure of the main memory database management system according to the present invention. In the present invention, the basic unit of dynamic allocation is designated as a block, and the address of the block is used as a basic element of the data structure. And, using the hierarchical structure of the level (level) to associate the address of the above-described blocks in a connection scheme starting from the lower node to the upper node. Here, the level, through the concept of hierarchy, refers to a nonlinear structure in which the upper layer includes all data of the lower layer, and the upper node includes the lower node as it is, and the nodes continue in the upper node. Are connected in series, and they are also included in more higher nodes.

And, the size of the block is determined by how many records are contained in one block because the records in the relation have the same size. Just do it.

As described above, in the present invention, by storing a predetermined number of records in a relation in one block, a subset of data can be continuously arranged in units of blocks, and dynamic allocation is a block that is a subset of data. Because it is executed only when specified, the number of dynamic allocations is reduced by the number of records in the block.

As described above, dynamically allocated blocks are managed based on block information. As shown in FIG. 1, a structure including block information includes root, level information (level_info), and level ( levels, records in blocks (records_in_block), and records size (recbuffer).

As described above, a pointer, which is a reference for a corresponding block when a search is stored, is stored in the root, and this value has the same value as the last block address of the level information for the lower level of the current level.

Information about each level is stored in the level information level_info. Assuming that the highest level is 4, level information for levels 1 to 4 is stored.

The current highest level is stored in the levels, the number of records in one block is stored in the number of records in the block (records_in_block), and the size of one record is stored in the record size (recbuffer).

As described above, block information is defined as follows.

typedef struct st_block / * Structure to manage levels and records * / {PTRS * root; / * Pointer to point to block in search * / struct st_level_info level_info [MAX_LEVELS + 1]; / * Structure to store information belonging to level * / unsigned int levels; / * Save the current highest level * / unsigned int records_in_block; / * Number of records in one block * / unsigned int record_size; / * Size of one record * /};

The level information, which is a component of the block information, includes the number of free blocks (free_ptrs_in_block) indicating the number of empty blocks in one level node, the number of records (records_under_level) indicating the maximum number of records included in one level, and last. It includes the last block address (last_blocks) indicating the start address of the block allocated as, if the level information is defined as follows.

struct st_level_info {unsigned int free_ptrs_in_block; / * Number of free blocks in one level node * // unsigned int records_under_level; / * Maximum number of records in one level * / PTRS * last_blocks; / * Address of last allocated block * /};

As described above, the block information is changed every time a block is allocated. When the level is increased from level 1 to level 2 at the time of block allocation, the level is changed from level 1 to level 2, as shown in FIG. As it increases, the root value that becomes a reference to the block during the search changes, which is the same value as the last block address in level 2's level information (level_info [1]), which does not change unless the level is increased. Do not.

On the other hand, in the present invention, as shown in Figure 2, using the hierarchical structure of the level to associate the address of the above-described blocks in a connection method starting from the lower node to the upper node, the address of the block is stored The data structure defined is as follows.

typedef struct st_ptrs {char * blocks [PTRS_IN_NOD]; / * An array containing the addresses of the blocks used at the level * /};

In addition, assuming that a node of level 1 (1_level) has N elements, a node of level 2 (2_level) has N elements in which nodes of level 1 (1_level) are elements, and level 3 (3_level). Node of level 2 has N elements as elements, and the same applies to more levels. Therefore, this is represented by Equation 2 below.

In equation (2), it is called N ^k at level K (K_level) is that the maximum number of data that can be stored in the current level one level N ^k. However, where it is the K-th level to note is not to assign as N ^k of the data size (N ^k dog * data size), and copies the data to that location, the maximum number of data that can be stored in the level K N ^k pieces, Dynamic allocation is done on a block basis. The information stored in each level is not data but represents the first address of blocks belonging to the level, and the blocks include blocks of lower levels.

3 is a flowchart illustrating a block allocation method of a main memory device database management system according to the present invention.

First, when a block is to be allocated to store a record, the number of free blocks (free_ptrs_in_block) included in the level information (level_info [i]) of each level is checked from a low level, that is, a level where free blocks exist. The free block number free_ptrs_in_block is searched for a level other than 0 (S10).

The index i used to express each level information level_info [i] in step S10 is expressed as a value of level-1, the level information of level1 is represented by level_info [0], and the level information of level2 is represented by It is represented by level_info [1].

Thereafter, the number of records to be stored in an empty block existing at the level retrieved in step S10 is determined, the block is allocated, and then the start address of the allocated block is assigned to a variable called root (S12).

Then, it is determined whether there is an allocated level, that is, whether the block allocation in the above-described process S12 is the first block allocation (S14).

In the case where the allocated level does not exist, that is, when the block allocation in the above-mentioned process S12 is the first block allocation, the level is set to 1 (S16), and the variable root of the block information is determined. (root) is assigned to the value assigned to the variable root ( root ) in step S12 described above (block-> root = root ), and the process S12 recalling the last block address (last_blocks) of variable level 1 information of the block information. Assign to the value assigned to the variable root ( root ) in (block-> level_info [0] .last_blocks = root ) (S18).

For example, assuming that the address of the block allocated in step S12 described above is 4e2a0 in hexadecimal, as shown in FIG. 1, the variable root is designated as 4e2a0 and the last block address of level 1 ( level_info [0] .last_blocks) is also designated 4e2a0.

On the other hand, if there is an allocated level as a result of the determination in step S14, that is, when the block allocation in step S12 is not the first block allocation, the index i and the block information of the level retrieved in step S10 are found. It is determined whether the variable levels included in are the same, that is, whether the level should be increased (S20).

As a result of the determination of step S20, when the index i of the level retrieved in step S10 and the variable levels included in the block information are the same, that is, when the level should be increased, the block information included in the block information is included. The value of the variable levels is set to a value 1 greater than the index i of the level retrieved in step S10 (block-> levels = i + 1), and the level information (level_info [i]) corresponding to the index i is set. Set the number of free blocks (free_ptrs_in_block) to N-1 (assuming a level node has N elements, one block is already allocated, so an empty block becomes N-1) (block- > level_info [i] .free_ptrs_in_block = N-1), when retrieving a block allocated in the above step S12, designates a pointer to the block as a variable root in the block information {(PTRS **) root [0 ] = block-> root)}. In addition, the address of the block used when searching for the block allocated in step S12 within the level is designated as the address (root) of the block allocated in step S12 (block-> root = root ). In step S12, the root of the block indicated by the allocated block is designated as the last block address of the level information having the index i (block-> root = block-> level_info [i] .last_blocks = root ++) (S22).

Subsequently, the process described above is multiplied by 4 bytes multiplied by N (assuming that a node at one level has N elements) of the address of the last allocated block in the last allocated block at the level at index i. {Block-> level_info [i] .last_blocks-> blocks [M] = (byte *) root} by adding the address (root) of the block allocated in S12 (S24).

On the other hand, when the determination result of the step S20 is that the index i of the level retrieved in the step S10 and the variable levels included in the block information are not the same, that is, the level does not need to be increased, Proceeding to step S24, the address of the last allocated block in the last allocated block at the level at index i is multiplied by 4 bytes by N (assuming that a node at a level has N elements). {Block-> level_info [i] .last_blocks-> blocks [N] = (byte *) root} by adding the address (root) of the block allocated in the above step S12.

After that, it is necessary to set an association relationship between the block allocated in step S12 and a block of a lower level belonging to the block. First, j, which is a value smaller than index i, is greater than 0, that is, It is determined whether a block exists (S26).

When j is greater than 0 as a result of the determination in step S26, that is, when there is a block of a lower level, the last block address of variable level [j] information of the block information is designated as the address of the block allocated at the current level. (Block-> level_info [j] .last_blocks = root ++), and in step S12, the address of the last allocated block in the last allocated block at the level with index j is multiplied by N multiplied by 4 bytes. {Block-> level_info [j] .last_blocks-> blocks [0] = (byte *) root}, and the number of free blocks of variable level [j] information of the block information. Is set to N-1 (block-> level_info [j] .free_ptrs_in_block = N-1) (S28), and j is decreased by 1 (S30), and the above process S28 to process j is not greater than 0. Repeat S30.

On the other hand, when j is not greater than 0 as a result of the determination in step S26, that is, when there is no lower level block, the last block address of the last block address of variable level 1 information of the block information is allocated at the lowest level. Specify the address (block-> level_info [0] .last_block = root) (S32).

For example, assuming that the address of the allocated block is 10000, the index i of the level of the block information and the level where the empty block exists is 3, and the root of the block information is 50000, the level of the block information is 4 Is changed to (= 3 + 1), and the number of free blocks (free_ptrs_in_block) of the level information level_info [3] corresponding to index 3 of the block information is 127 (assuming that a node of one level has 128 elements, Since one block is already allocated, an empty block becomes 127).

Then, the variable root in the block information is designated as 50000, 10000 is designated as the address of the block used in the level, and the root of the block indicated by the allocated block is the last block address of the level having an index of 3 and the assigned block. It is specified as 10512 (= 128 * 4 + 10000), which is a step incremented from the address, and the address of the last allocated block within the last allocated block at the level with index 3 is 10512 (= 128 * 4 + 10000). It is designated as.

Then, the last block address of level information (level_info [2]) corresponding to index 2 is set to 10000 to establish an association with the lower level, and finally, the last block in the last allocated block at the level having index 2 Set the address of the allocated block to 10512 (= 128 * 4 + 10000), and set the number of free blocks to 127.

Then, the last block address of the level information (level_info [1]) corresponding to index 1 is designated as 10512, and the address of the last allocated block in the last allocated block at the level of index 2 is 11024 (= 128). 4 + 10512), and sets the number of free blocks to 127.

The last block address of level information (level_info [0]) corresponding to index 0 is designated as 11024.

4 is a flowchart illustrating a record retrieval method of the main memory device database management system according to the present invention.

First, a block whose index is the quotient of the operation obtained by dividing the index m of the record to be searched by the maximum number of records that can be included in the lower level of the highest level is found at the highest level (S40).

Substituting the remainder obtained as a result of the operation of step S40 into m, a block is indexed at a lower level where the quotient of the operation obtained by dividing m by the maximum number of records that can be included in the next lower level is indexed (S42).

The process S42 is repeatedly performed while descending to a lower level by one step until a block in which the search record exists is found (S44).

As described above, after locating the block where the record to be searched is located through the process S40 to S44, the search record is based on the start address of the last searched block, the remaining values finally substituted into m, and the record size. In calculating the address (S46), the address of the search record becomes the value obtained by multiplying the record size by the remaining remaining m and adding the start address of the last searched block.

For example, the maximum number of records that can be included in level 1 is 10, the maximum number of records that can be included in level 2 is 100, the maximum number of records that can be included in level 3 is 1000, and the records can be included in level 4 Assuming that the maximum number of times is 10000 and the current top level is level 4, for example, to find the address of the 1234th stored record, the position index [1234] of the record to be searched is set to the level 4 of the current top level. Find the block [block 1 of level 4] indexed by the quotient [1] divided by the maximum number of records [1000] that can be contained at the lower level, Level 3, and the rest [234] as the lower level of Level 3. Find the block [block 2 of level 3] indexed by the quotient [2] divided by the maximum number of records [100] that can be included in level 2, and the rest [34] to be the lower level of level 2. Maximum level that can be included in 1 DE can and finds a block Levels # 3 of the block; Seeking blocks containing the record to be searched exists by performing the process of the quotient [3], divided by the index [10].

Since the rest [4] indicates how many records exist to be searched in the searched block, it is assumed that the start address of block 3 of level 2 is 50000 and the record size is 40. The address of is equal to the remainder [4] multiplied by the record size [40] plus the start address [50000] of the retrieved block [50160].

For example, if you want to know the address of the 2000th stored record, the maximum number of records that can contain the position index [2000] of the record to be searched at level 3, which is a lower level of level 4, which is the current highest level [1000]. Find the block [block 2 of level 4] indexed by the quotient [2] divided by. The remainder [0] divided by the maximum number of records [100] that can be included in level 2, the lower level of level 3. Find the block [block 0 of level 3] with index [0] and divide the remainder [0] by the maximum number of records [10] that can be included in level 1, which is a lower level of level 2. A block [block 0 of level 2] whose index is 0] is searched to find a block in which a record to be searched exists.

Since the rest [0] indicates how many records exist to be searched in the searched block, it is assumed that the start address of block 0 of level 2 is 10000 and the size of the record is 40. The address of is equal to [1000] obtained by multiplying the record size [40] by the remaining [0] and the starting address [10000] of the searched block.

The data structure, block allocation, and record retrieval method of the main memory device database management system of the present invention are not limited to the above-described embodiments, and various modifications can be made within the scope of the technical idea of the present invention.

According to the data structure and the block allocation and record retrieval method of the main memory database management system of the present invention as described above, by designating the basic unit of dynamic allocation as a block, by managing the address of each block in a hierarchical structure As a result, a subset of the data can be arranged in blocks, and the number of dynamic allocations is reduced by the number of records in the block.

Therefore, overhead can be reduced as compared with the conventional method of manipulating data individually.

In addition, by managing block addresses in a hierarchical structure, data retrieval and pointer management are simplified, thereby improving performance and speed.

Claims (9)

Designates the basic unit of dynamic allocation as a block, and associates the addresses of the blocks using a hierarchical structure called a level, where the level is an exponential structure containing all data of a lower level. The data structure of the system. The method of claim 1, wherein the size of the block, The data structure of a main memory database management system, which is determined by how many records are contained in one block. The method of claim 1, wherein the blocks, A pointer which becomes a reference to the corresponding block when searching; Level information for each level; With the current highest level; The number of records in one block; A data structure of a main memory database management system, which is managed based on block information including one record size. The method of claim 3, wherein the level information, The number of empty blocks in one level node; The maximum number of records included in one level; The data structure of a main memory database management system, comprising the address of the last allocated block at that level. Checking the level information from the low level, searching for the level in which empty blocks exist, determining the number of records to be stored in the block, allocating blocks, and assigning the address of the allocated block to a variable called root; ; If the assigned level does not exist according to the existence of the assigned level, allocating a new level; Increasing the level when the level is increased according to whether the level is increased when there is an assigned level; If the level is not increased, the process of designating the address of the last allocated block in the last allocated block at the lower level of the current level as N multiplied by 4 bytes and the address of the allocated block; ; Setting an association relationship between the current level and the lower level when the lower level exists according to the existence of the lower level; And when the lower level does not exist, assigning the last block address of the lower level as the address of the allocated block. The method of claim 5, wherein the new allocation of the level comprises: Setting the level of block information to 1, assigning a pointer to a value assigned to the variable named root, and assigning the last block address of level information of level 1 to a value assigned to the variable named root. Block allocation method of a main memory database management system. The method of claim 5, wherein the step of increasing the level, Increasing the level of block information by 1, setting the number of empty blocks included in the increased level to N-1, and designating a pointer as a reference indicating the allocated block as a root value of a predetermined block; and; Designating an address of the allocated block as an address of a block used at a current level, and designating an address of the allocated block as a root of a block indicated by the allocated block; A main memory device, comprising: assigning the address of the last allocated block in the last allocated block at the current level to N, multiplied by 4 bytes, and the address of the allocated block; Block allocation method for database management system. The method of claim 5, wherein the establishing of the association relationship comprises: The last block address of the lower level is designated as the address of the last allocated block at the upper level of the lower level, and the address of the allocated block within the allocated block is multiplied by N times 4 bytes of the allocated block. Assigning an address as a value, and repeatedly setting the number of empty blocks included in the lower level to N-1 to an upper level of the lowest level; And assigning the last block address of the lowest level to the address of the block allocated last from the upper level of the lowest level. Retrieving at the top level a block whose index is the quotient of the operation obtained by dividing the index of the record to be searched by the maximum number of records that can be included in the lower level of the highest level; Searching for a block in the lower block by assigning the remainder of the operation to the index and quoting a block whose index is the quotient of the operation by dividing the index by the maximum number of records that can be included in the next lower level of the lower level. Repeatedly performing the steps down to a lower level until a block in which a desired record exists is found; And calculating an address of a search record based on a value finally inserted into the index, a record size, and an address of a last searched block.