論文 / 著書情報
Article / Book Information
Title

A Concurrency Control Method for Parallel Btree Structures

AuthorTomohiro Yoshihara, Dai Kobayashi, Ryo Taguchi, Haruo Yokota

Journal/Book nameProc. of International Special Workshop on Databases For Next
Generation Researchers (SWOD 2006), Vol. , No. , pp. 71-76

Issue date

2006, 4DOI

10.1109/ICDEW.2006.7

URL

http://www.ieee.org/index.html

Copyright(c)2006 IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other users, including
reprinting/republishing this material for advertising or promotional
purposes, creating new collective works for resale or redistribution toservers or lists, or reuse of any copyrighted components of this work inother works.

Note

このファイルは著者（最終）版です。
This file is author (final) version.

Powered by T2R2 (Science Tokyo Research Repository)

A Concurrency Control Method for Parallel Btree Structures

Tomohiro Yoshihara
11

Dai Kobayashi

1

2

Ryo Taguchi

Haruo Yokota

3,1Department of Computer Science, Graduate School of Information Science and Engineering,Tokyo Institute of Technology
22121 Ookayama, Meguro-ku, Tokyo 1528552, Japan

Science and Technical Research Laboratories, Japan Broadcasting Corporation
11011 Kinuta, Setagaya-ku, Tokyo 1578510, Japan3

Global Scientic Information and Computing Center, Tokyo Institute of Technology
2121 Ookayama, Meguro-ku, Tokyo 1528550, Japan{yoshihara,daik}@de.cs.titech.ac.jp, taguchi.r-cs@nhk.or.jp, yokota@cs.titech.ac.jp
Abstract

data partitioning methods are signicant [3, 4]. The value
range partitioning method with a parallel Btree structure is

A new concurrency control protocol for parallel Btree
structures, MARK-OPT, is proposed.

MARK-OPT marks

the lowest structure-modication-operation (SMO) occurrence point during optimistic latch coupling operations, toreduce the cost of SMO compared to the conventional protocols such as ARIES/IM and INC-OPT. The marking reduces the frequency of restarts for spreading the range of
X latches, which will clearly improves the system throughput. Moreover, the MARK-OPT is deadlock free and satises the physical consistency requirement for Btrees. These
indicate that the MARK-OPT is right and suitable as a concurrency control protocol for Btree structures. This paper
also proposes three variations of the protocol, INC-MARKOPT, 2P-INT-MARK-OPT and 2P-REP-MARK-OPT, by focusing on tree structure changes from other transactions.
We implement the proposed protocols, the INC-OPT, and
the ARIES/IM for the Fat-Btree, a form of parallel Btree,
and compare the performance of these protocols using alarge-scale blade system.

The experimental results indi-cate that the proposed protocols always improve the systemthroughput, and the 2P-REP-MARK-OPT is the most useful protocol in a high update environment. Moreover, in theexperiment, the low frequency of restarts in the proposed
protocols indicates that the marking in the proposed proto-

an excellent approach to handle the skews, as it also provides clustering I/Os and fast access paths for both exact
match and range queries.
To make the parallel Btree practical, it is important toconsider the cost of update operations requiring concurrent
accesses to multiple PEs. If all PEs have copies of a single
Btree, the synchronization between the PEs degrades thesystem throughput considerably. On the other hand, if allindex nodes of a Btree are only placed on a single PE, thePE becomes a bottleneck in parallel processing due to theconcentration of all index accesses to it. To resolve these
problems, an update conscious parallel Btree structure, FatBtree, has been proposed, and experimental results indicatethat Fat-Btrees provide better performance than other parallel Btrees [12].
It is also important to provide an efficient concurrency
control protocol for parallel Btree structures, including FatBtree. The INC-OPT protocol suited for a parallel Btree ona shared-nothing parallel machine has been proposed [8].
The INC-OPT protocol outperforms the conventional Btree
concurrency control protocols, such as the B-OPT protocol [1] and the ARIES/IM protocol [9].

However, thecosts of spreading an X latch in the protocol are still highcols is effective.

when structure modication operations (SMOs) occurred1

protocol for parallel Btree structures, MARK-OPT. It re-frequently, which degrades the total performance.
In this paper, we propose a new concurrency control

Introduction

duces the frequency of restarts retraversing from the root

In a shared-nothing parallel machine for database systems, retrievals and updates are performed in parallel ona processing element (PE) storing the object data. Bottlenecks on highly accessed PEs by access-request skew degrade system performance.

To improve the performance,

node compared with the INC-OPT protocol. We also propose three variations of the protocol, INC-MARK-OPT, 2PINT-MARK-OPT and 2P-REP-MARK-OPT, focusing on
the tree structure changes caused by other transactions.
We implemented the four proposed protocols, the INC-

root page

Table 1. Latch matrix
Mode

IS

IX

S

SIX

X

IS
IX

index pageS
SIX

leaf page

X
PE0

PE1

PE2

PE3

2.2

Concurrency Control Methods

Figure 1. Fat-Btree
Some concurrency control method for the Btree is necessary to guarantee its consistency. Instead of locks, fast and
OPT and the ARIES/ IM

1on an autonomous disk sys-

simple latches are usually used for concurrency control dur-tem [11] using the Fat-Btree as the distributed directory

ing traversing index nodes in a Btree [5]. A latch is a form

structure and measured the system throughput with chang-of semaphore and the latch manager does not have a dead-ing update ratio. These experimental results indicate thatlock detection mechanism. Therefore, concurrency control

the proposed protocols are effective.

for a Btree node should be deadlock free.

The remainder of the paper is organized as follows. First,

In this paper, a latch is assumed to have ve modes: IS,

the concept of the Fat-Btree and the concurrency controls

IX, S, SIX, and X as shown in Table 1 [5]. The symbol offor parallel Btrees are introduced as background in section means that the two modes are compatible.

2. We propose the new concurrency control protocols for

Because a parallel Btree structure, including the Fat-parallel Btree structures in section 3. The experimental re-

Btree, has duplicated nodes a special protocol for the dis-sults are reported in section 4. The nal section presents thetributed latch manager is required to satisfy the latch se-conclusions of this paper.

mantics.

Requested IS and IX mode latches can be pro-

cessed only on a local PE, whereas the other modes have to2

Background

2.1

Fat-Btree Structure

The Fat-Btree [12] is a form of parallel Btree in which+
the leaf pages of the B -tree are distributed among PEs andeach PE has a subtree of the whole Btree, which contains
the root node and intermediate index nodes between the root
node and leaf nodes allocated to the PE. Figure 1 shows anexample of a Fat-Btree using four PEs.
Although the number of copies increases with proximity
to the root node in a Fat-Btree, the update frequency of thesenodes is relatively low. On the other hand, leaf nodes have arelatively high update frequency but have no copy. Consequently, the nodes to be updated more frequently have lower
overhead for updating with respect to the synchronization
between duplicated nodes.
Moreover, in the Fat-Btree, index pages are only necessary for searching for the leaf pages stored in each PE.
Therefore, the Fat-Btree can have a high cache hit rate if
the index pages are cached in each PE. Because of the highbe granted on all the PEs storing the duplicated nodes to belatches. That is, the IS and IX modes have much smaller
synchronization cost than the S, SIX and X modes, which
require communication between the PEs. The S, SIX, and X
mode latches on remote copies are acquired by using theirpointers. In addition, such latches have to be set in linear
order to avoid dead lock. This means synchronization cost
grows in proportion to the number of PEs related to latches.
The following conditions of the concurrency controls forparallel Btrees are proposed in [8].
Condition 1.

A concurrency control method for parallel

Btrees should satisfy the following conditions:(a) No concurrency control protocol method for index
nodes, which cause deadlocks, should be used.
(b) Use of S, SIX, and X mode latches on index nodes at
upper levels of the Btree should be avoided as much as
possible.
(c) The entire tree should not be latched, even for a shortduration.

cache hit rate the update processes and the search processes

B-OPT [1], OPT-DLOCK [10], and ARIES/IM [9] arecan be processed quickly, compared with a conventional

excellent concurrency control methods for a Btree on a sin-parallel Btree structure.

gle machine. However, they do not satisfy Condition 1: B-

1

We implemented ARIES/IM based on [9], but did not recovery mech-anism of it because we do not focus on recovery in this paper.

OPT does not satisfy Condition 1-(b), OPT-DLOCK does
not satisfy Condition 1-(a), and ARIES/IM does not satisfy

Condition 1-(c). Therefore, these concurrency controls are

SMO occurrence point during optimistic latch coupling op-

unsuitable for parallel Btrees, such as Fat-Btree.

erations. We call this the marking optimistic (MARK-OPT)

2.3

INC-OPT Protocol

protocol, which improves the response time by reducing thefrequency of restarts.

In addition, the MARK-OPT pro-duces high system throughput because of the reduction of
The INC-OPT protocol satisfying Condition 1 has been
proposed [8] as a concurrency control protocol for parallel

middle phases for spreading an X latch and removes needless X latches.

Btrees, including Fat-Btree.
The INC-OPT protocol to search for a key is simple. An
IS mode latch is held on the root node initially, then the fol-

The procedure MARK-OPT uses to search for a key isidentical to INC-OPT, whereas its update consists of the following two phases:

lowing steps are performed during traversal in the parallel
The rst phase: The traverse reaches a leaf with latch-

Btree:

coupling with the IX latches. If the index node is full,

1. Derive a pointer to a child node by comparing the key

MARK-OPT marks the height of the node from thein the parent node.

root node. Whenever the index node is full, the marking height is updated one by one. On the leaf, an X

2. Acquire an IS mode latch on the child, and release thelatch is acquired. If the leaf node is not full, the up-

latch on the parent.

dater updates it. If the leaf node is full, a split occurs
3. Repeat the above steps until the traverse reaches a leafin the leaf, this latch is released immediately and thennode.
The above procedure is usually called latch-coupling [5].
When the traverse arrives at a leaf node, it acquires an S

the procedure shifts to the second phase.
The second phase: The height of the tree is marked asin the rst phase.

latch on the leaf and reads data from it.

MARK-OPT tries to acquire the

X mode latches on the leaf node and the index node

The INC-OPT protocol for an update consists of two

below the height marked in the previous phase.

phases.

If

the nodes involved by SMOs are not protected by X

The rst phase: The traverse reaches a leaf with latch-

latches, it releases all latches and restarts. This pro-coupling with the IX latches. At the leaf, an X latch

cess continues until all the nodes involved by SMOs

is acquired. If the leaf node is not full, the updater up-

are protected by X latches.

dates it. Otherwise, if the leaf node is full it splits, thisMore precisely, the level of node (h) is one for the root

latch is once released and it then shifts to the second
phase.

node, and H for the leaf node where H is the height of
the tree. When l denotes the level of the Btree where the

The second phase: The INC-OPT tries to acquire the X

MARK-OPT has to start to use X latches, the variable l ismode latches on the lower two nodes, i.e., the leaf nodeinitially set to H. The height marked during a traverse is de-and its parent, with the X mode latches. If the parent

noted by m. The MARK-OPT protocol is shown in Figure

node also causes an SMO, it releases all latches and2.

tries to acquire the X mode latches on the lower three

Because MARK-OPT decided the range of the X latch,nodes. This process continues until all the nodes in-based on the state of the previous phase obtained by mark-volved by SMOs are protected by X latches.

ing, it may require multiple restarts when SMOs have

The INC-OPT protocol is precisely dened in [8].

spread. However, the number of maximum phases in the

When an SMO occurs, the INC-OPT may need multiple

INC-MARK-OPT is H at most as for INC-OPT. MARK-

restarts. When the root node causes an SMO, the INC-OPTOPT requires only a restart once in many cases because

requires as many phases as the height of the Btree. This

SMOs rarely spread. Therefore, MARK-OPT does not re-increases the response time of the update operations. In ad-quire many restarts like INC-OPT even when SMOs occur

dition, it decreases the system throughput because of theon nodes at upper levels.

multiple X latches used on the index nodes at upper levels.

The MARK-OPT protocol satises Condition 1 in 2.2.
The reasons are:3

Proposed Protocols

3.1

MARK-OPT Protocol

1. It is deadlock free because it acquires latches topdown.
2. It does not latch the index nodes with the S, SIX

We propose a new concurrency control protocol for parallel Btrees, including Fat-Btree, which marks the lowest

modes, and does not acquire needless X mode latches
on nodes not relating to SMOs.

→

1
2

The rst phase3

IX latch on Child, unlatch Parent;

5

if Child is not full then

6
7
8
9

←
→

m := h;/* Marking */Table 2. Comparison of protocols by handlingfor a tree structure change between phases

Determine NewChild;

Parent := Child; Child := NewChild; h := h + 1;
end;

continue

shift tothe 2nd phasethe 1st phase10

X latch on Child and its copies;

11

Unlatch Parent;non-

MARK-OPT

12

if Child is full thenrestart/ INC-OPT

14else begin

restart

INC-MARK-OPT

15

Update;

16
17
18
19

Release all granted latches; l := m;Parent := null; Child := ROOT; h := 1; m := 1;
while h < l do begin

IX latch on Child, unlatch Parent;
if Child is not full then24m := h;/* Marking */Determine NewChild;

Parent := Child; Child := NewChild; h := h + 1;

25

end;

26

X latch on Child and its copies;

27

Unlatch Parent;

28

Determine NewChild;

29
30
31
32
33
34
35
36
37

Parent := Child; Child := NewChild; h := h + 1;
while h ≤ H do begin

the protocols judges if the tree structure has changed, andthe rows indicate the presence of a restart at that time.
Because these extension protocols mark the height of thetree as does MARK-OPT, they execute very similar process
as MARK-OPT except for phase change. All of these alsosatisfy Condition 1.

X latch on Child and its copies;
Determine NewChild;

Parent := Child; Child := NewChild; h := h + 1;
end;

3.2.1

INC-MARK-OPT Protocol

if X latch are not sufficient for SMOs thenRelease all granted latches; l := m; goto 18;

else begin

38

Update including the SMOs;

39

Release all granted latches; operation completion;

40

2P-REP-MARK-OPT

Release all granted latches; operation completion;

21
23

2P-INT-MARK-OPT

end;

20
22

The second phase

while h < l do begin

4

13

←

l := H;

Parent := null; Child := ROOT; h := 1; m := 1;

end;

The incremental marking optimistic (INC-MARK-OPT)
protocol restarts when it judges that the tree structure haschanged in the second phase. In this case, the height marked
for next phase is not complete because traverse does not

Figure 2. The MARK-OPT protocol

reach a leaf node. However, the INC-MARK-OPT decides
the range of the X latch based on that information.
The second phase of the INC-MARK-OPT protocol for

3. It never uses a tree latch.

update is as follows.

The INC-MARK-OPT acquires the

X mode latches on the node marked in the previous phase.

It is easy to prove that the MARK-OPT satises the

If the node is not full, it executes a process similar to thephysical consistency requirement for Btrees. When an up-

MARK-OPT to the leaf node. If the node is full, it releases

dater realizes that it does not acquire all required X latches

all latches and restarts. This process continues until all thefor the SMOs, the updater releases all the latches without

nodes involved by SMOs are protected by X latches.

modifying any data. Thus, the MARK-OPT essentially fol-

If the INC-MARK-OPT judges that the tree structurelows the two phase locking (2PL). The 2PL ensures thehas been changed, it restarts at once. Therefore, the INC-

physical consistency of the Btree structure for each up-

MARK-OPT does not acquire more needless X latches thandate [2].

MARK-OPT when SMOs have actually spread.

On theother hand, the INC-MARK-OPT may judge that the tree

3.2

Extensions of the MARK-OPT

structure has changed when SMOs have contracted.

Inthat case, the INC-MARK-OPT acquires more needless X
We propose three variations of the concurrency control
protocol, INC-MARK-OPT, 2P-INT-MARK-OPT and 2PREP-MARK-OPT, which are extensions of MARK-OPT.
In each protocol only the second phase of the update protocol is different. MARK-OPT does not change the processlatches than MARK-OPT. Moreover, INC-MARK-OPT increases the frequency of restarts compared with MARKOPT. However, the number of maximum phases in the INCMARK-OPT is H at most the same as MARK-OPT because
it spreads the range of the X latch at each restart.

even if the tree structure is changed by other transactions.
On the other hand, the extension protocols look at the stateof the node rst latched with the X mode in that phase and

3.2.2

2P-INT-MARK-OPT Protocol

checks the change from the previous phase of a subtree re-

The 2-phase integrated marking optimistic (2P-INT-MARK-

lating to SMO. If the extension protocols judge that the tree

OPT) protocol performs the latch-coupling with IX latches

structure has been changed, each protocol executes a dif-

below the node when it judges that the tree structure has

ferent process. The difference in the processes is shown inchanged in the second phase. That is, it returns to the rst

Table 2. The columns indicate the process phases, because

phase. Because the MARK-OPT marks the tree state in thesecond phase, it shifts to the rst phase without the problemof marking that is incomplete.
The second phase of the 2P-INT-MARK-OPT protocol
for update is as follows. The 2P-INT-MARK-OPT acquires
the X mode latches on the node marked in the previous
phase. If the node is not full, it executes a process similar to MARK-OPT to the leaf node. If the node is full, it
shifts to the rst phase on the node.
If the 2P-INT-MARK-OPT judges that the tree structure

Table 3. Experimental Environment
No. of Nodes:

128 (Storages), 16 (Clients)

CPU:

AMD Athlon XP-M 1800+ (1.53GHz)

Memory:PC2100 DDR SDRAM 1GB

Hard Drive:

TOSHIBA MK3019GAX

OS:

Linux 2.4.20

Java VM:

Sun J2SE SDK 1.5.0 01 Server VM(30GB, 5400rpm, 2.5inch)

has changed, it shifts to the rst phase. Therefore, the 2PINT-MARK-OPT decreases the frequency of restarts to agreater extent than the INC-MARK-OPT and it does not acquire more needless X latches than MARK-OPT. Moreover,
2P-INT-MARK-OPT does not acquire needless X latches
when SMOs have contracted. On the other hand, the 2PINT-MARK-OPT may require more restarts than H, theheight of the tree. However, this will happen infrequently.

Table 4. Parameters used for the experiments
Page size:

4KB

Tuple size:

3KB

Max No. of entries in an index node (fanout):

8

Max No. of tuples in a leaf node:1

In the worst case, the 2P-INT-MARK-OPT cannot complete the process but the 2P-INT-MARK-OPT requires onlya small number of restarts because this will not happen in

4.1

Experimental Environment

practice.
We used an experimental system of the autonomous disk
3.2.3

2P-REP-MARK-OPT Protocol

The 2-phase repetitive marking optimistic (2P-REP-MARKOPT) protocol restarts when it judges that the tree structure
has changed in the second phase.

The 2P-REP-MARK-OPT returns to the rst phase after it restarts.
The second phase of the 2P-REP-MARK-OPT protocol for update is as follows. The 2P-REP-MARK-OPT acquires the X mode latch on the node marked in the previous
phase. If the node is not full, it executes a process similar to
MARK-OPT to the leaf node. If the node is full, it releases
all latches and it executes the process in the rst phase on
the root node.
If the 2P-REP-MARK-OPT judges that the tree structure has changed, it restarts at once and shifts to the rst
phase.

Therefore, the 2P-REP-MARK-OPT acquires theleast needless X latches of the proposed protocols although
it increases the frequency of restarts more than any of the
proposed protocols. As well as 2P-INT-MARK-OPT, the
2P-REP-MARK-OPT may require more restarts than H, theheight of the tree. However, the 2P-REP-MARK-OPT requires only a small number of restarts because this is unlikely to happen in practice.

4

Experiments

distributed storage technology we proposed.

The experi-mental system was implemented on a 144 node blade system using the Java programming language on Linux. We
used 128 nodes for storing data and 16 nodes as clients
sending requests.

A preliminary experiment showed thatthe backbone network switch had adequate performance.
The experimental environment is summarized in Table 3.
Table 4 shows the basic parameters we set for the experiments. These parameters were chosen to distinguish clearly
the differences between the protocols.

4.2

Experimental Result

Sixteen clients (thirty-two threads in parallel per blade)sent requests to PEs containing the Fat-Btree with 256 tuples per PE, for 60 seconds. The access frequencies were
uniform. Figure 3 shows the performance of the six concurrency controls as the update ratio changes from 0% through100%.

The solid lines show the performance of the four

proposed protocols, the dotted line shows the performanceof INC-OPT and the dashed line shows the performance of
ARIES/IM. The horizontal and vertical axes are the update
ratio and throughput, respectively.
When the update ratio was 0%, the results of all protocols were virtually the same.

This is because the con-currency controls used to retrieve data are basically the
To show that MARK-OPT and its extension protocols

same. But, the throughput of ARIES/IM decreases sharply

are effective, we implemented them on an autonomous diskeven though the increase in the ratio of update operations is

system [11] on a blade system, which uses the Fat-Btree,small. This is because the cost of global synchronization by

and evaluated their performance under a number of condi-

using the tree latches for SMOs caused by the update op-

tions.

erations. On the other hand, when the update ratio is low, 

BDC FEHGI!KJML
NPOQ G BDC FEHGR!KJMLSJMG NPO LTG BDC FEHGI!UJLSJMGVXWYJG BDC XEHGI!KJML
NPOQ GR!KJL
C N WYZ\[ NPB

  
@ =A

 

lent concurrency control. The B-link uses links to chain all
nodes at each level together. In the B-link algorithm, neither readers nor updaters latch-couple on their way down

=3

  
5;?

 

to a leaf node and they acquire the latch only on one node

=3

  

at a time. Moreover, the B-link algorithm does not require

:49 ;

 

restarts and they complete processing during one traverse.

  

We need to examine how to apply the B-link to the Fat-

Btree and compare this and the conventional protocols.

8
:9
>

<8
6

2487

56

1243

 



 !"#%$&'(*)#+-,/.0

Acknowledgments 

We thank Dr.

Figure 3. Comparison of concurrency control
protocols with changing update ratio

Jun Miyazaki of NAIST for his advice

on concurrency control for the Fat-Btree.

This work is

partially supported by CREST of JST (Japan Science andTechnology Agency), SRC (Storage Research Consortium),a Grant-in-Aid for Scientic Research from MEXT Japan(#16016232) and the Tokyo Institute of Technology 21COE

the results of all other protocols were better than that of
ARIES/IM and almost the same. However, the throughput

Program Framework for Systematization and Applicationof Large-Scale Knowledge Resources.

of the INC-OPT decreases as the update ratio increases. In
contrast to the INC-OPT, the proposed protocols can pro-

References

vide reasonable throughput although the update ratio increases. The decline in the throughput of the proposed protocols is much slower than that of INC-OPT even when the
update operations are included.

This is because the pro-

posed protocols reduce the frequency of restarts comparedwith the INC-OPT when SMOs occur, although the increasein the update ratio increases the occurrence of SMOs.
In

thecomparison

of

the

proposed

protocols,[1] R. Bayer and M. Schkolnick. Concurrency of Operations on
B-trees. Acta Inf., 9(1):121, 1977.
[2] P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. AddisonWesley, 1987.
[3] G. Copeland, W. Alexander, E. Boughter, and T. Keller. Data
Placement in Bubba. In Proc. of ACM SIGMOD'88, pages

the99108, 1988.

throughput of 2P-REP-MARK-OPT is the highest, when

[4] S. Ghandeharizadeh and D. J. DeWitt. Hybrid-Range Par-the update ratio is 100%. Then, the throughput of 2P-INT-

titioning Strategy: A New Declustering Strategy for Multi-

MARK-OPT is next highest and then MARK-OPT is higher

processor Database Machines. In Proc. of VLDB'90, pages

than INC-MARK-OPT. The throughput of the INC-MARKOPT is the lowest. Therefore, the 2P-REP-MARK-OPT is
the most effective when many SMOs occur.

481492, 1990.
[5] J. Gray and A. Reuter. Transaction Processing: Concepts
and Techniques. Morgan Kaufmann, 1992.
[6] V. Lanin and D. Shasha.

A Symmetric Concurrent B-tree

Algorithm. In Proc. of FJCC'86, pages 380389, 1986.

5

Conclusion[7] P. L. Lehman and S. B. Yao.

Efficient Locking for Con-

current Operations on B-trees. ACM Trans. Database Syst.,
6(4):650670, 1981.

We propose a new concurrency control, MARK-OPT, forparallel Btrees, for the shared-nothing environment. When
SMOs occur, the proposed protocol marks the node forwhich the X latch should be acquired rst and it acquires the
X latch nodes below the marked height after it restarts. We
also propose three extensions of the MARK-OPT protocol.
In addition, we have experimented on an autonomous disk

[8] J. Miyazaki and H. Yokota. Concurrency Control and Performance Evaluation of Parallel B-tree Structures.
[9] C. Mohan and F. Levine.

ARIES/IM: An Efficient andHigh Concurrency Index Management Method Using WriteAhead Logging. In Proc. of ACM SIGMOD'92, pages 371
381, 1992.
[10] V. Srinivasan and M. J. Carey.

system implemented on a large-scale blade system to com-

Concurrency Control Algorithms.

pare the four proposed protocols and the conventional pro-

MOD'91, pages 416425, 1991.

tocols. The experimental results indicated that the proposed
protocols were effective and 2P-REP-MARK-OPT was thesuperior protocol.
In future studies we plan to apply the B-link [7, 6] to the
Fat-Btree.

It is known that the B-link can achieve excel-

IEICE

Trans. Inf. Syst., E85-D(8):12691283, 2002.

Performance of B-Tree
In Proc. of ACM SIG-

[11] H. Yokota. Autonomous Disks for Advanced Database Applications. In Proc. of DANTE'99, pages 435442, 1999.
[12] H. Yokota, Y. Kanemasa, and J. Miyazaki. Fat-Btree: An
Update-Conscious Parallel Directory Structure. In Proc. of
ICDE'99, pages 448457, 1999.