山东大学计算机科学与技术学院数据库系统英文课件 ch11

DatabaseSystem

Concepts,

6th

Ed.©Silberschatz,

Korth

and

SudarshanSee

www.db-

for

conditions

on

re-useChapter

11:

Indexing

and

HashingChapter

12:

Indexing

and

Hashing11

.

2©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Basic

Conceptsn

Ordered

Indicesn

B+-Tree

Index

Filesn

B-Tree

Index

Filesn

Static

Hashingn

Dynamic

Hashingn

Comparison

of

Ordered

Indexing

and

Hashingn

Index

Definition

in

SQLn

Multiple-Key

AccessIndex

Evaluation

Metrics11

.

4©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Access

types

supported

efficiently.

E.g.,l

records

with

a

specified

value

in

the

attributel

or

records

with

an

attribute

value

falling

in

a

specified

rangeof

values.n

Access

timen

Insertion

timen

Deletion

timen

Space

overheadOrdered

Indices11

.

5©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

In

an

ordered

index,

index

entries

are

stored

sorted

on

the

searckey

value.

E.g.,

author

catalog

in

library.n

Primary

index:

in

a

sequentially

ordered

file,

the

index

whosesearch

key

specifies

the

sequential

order

of

the

file.l

Also

called

clustering

indexl

The

search

key

of

a

primary

index

is

usually

but

notnecessarily

the

primary

key.n

Secondary

index:

an

index

whose

search

key

specifies

an

orderdifferent

from

the

sequential

order

of

the

file.

Also

callednon-clustering

index.n

Index-sequential

file:

ordered

sequential

file

with

a

primary

indDense

Index

Files11

.

6©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Dense

index

—

Index

record

appears

for

every

search-keyvalue

in

the

file.n

E.g.

index

on

ID

attribute

of

instructor

relationDense

Index

Files

(Cont.)11

.

7©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Dense

index

on

dept_name,

with

instructor

file

sorted

ondept_nameSparse

Index

Filesn

Sparse

Index:

contains

index

records

for

only

some

search-key

values.l

Applicable

when

records

are

sequentially

ordered

on

search-keyn

To

locate

a

record

with

search-key

value

K

we:l

Find

index

record

with

largest

search-key

value

<

Kl

Search

file

sequentially

starting

at

the

record

to

which

theindex

record

points11

.

8©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionSparse

Index

Files

(Cont.)n

Compared

to

dense

indices:l

Less

space

and

less

maintenance

overhead

for

insertions

anddeletions.l

Generally

slower

than

dense

index

for

locating

records.n

Good

tradeoff:

sparse

index

with

an

index

entry

for

every

blockin

file,

corresponding

to

least

search-key

value

in

the

block.11

.

9©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionSecondary

Indices

ExampleSecondary

index

on

salary

field

of

instructorn

Index

record

points

to

a

bucket

that

contains

pointers

to

allthe

actual

records

with

that

particular

search-key

value.n

Secondary

indices

have

to

be

dense11

.

10©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionPrimary

and

Secondary

Indices11

.

11©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Indices

offer

substantial

benefits

when

searching

forrecords.n

BUT:

Updating

indicesimposesoverhead

on

databasemodification

--when

afile

ismodified,

every

index

on

thefile

must

be

updated,n

Sequential

scan

usingprimaryindex

is

efficient,

but

asequential

scan

using

a

secondary

index

is

expensivel

Each

record

access

may

fetch

a

new

block

from

diskl

Block

fetch

requires

about

5

to

10

milliseconds,

versusabout

100

nanoseconds

for

memory

accessMultilevel

Index11

.

12©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

If

primary

index

does

not

fit

in

memory,

access

becomesexpensive.n

Solution:

treat

primary

index

kept

on

disk

as

a

sequentialfile

and

construct

a

sparse

index

on

it.l

outer

index

–

a

sparse

index

of

primary

indexl

inner

index

–

the

primary

index

filen

If

even

outer

index

is

too

large

to

fit

in

main

memory,

yetanother

level

of

index

can

be

created,

and

so

on.n

Indices

at

all

levels

must

be

updated

on

insertion

ordeletion

from

the

file.Multilevel

Index

(Cont.)11

.

13©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionIndex

Update:Deletionn

If

deleted

record

was

theonly

record

in

the

file

withits

particular

search-keyvalue,

the

search-key

isdeleted

from

the

indexn

aSlisnog.le-level

index

entry

deletion:l

Dense

indices

–

deletion

of

search-key

is

similar

to

filerecord

deletion.l

Sparse

indices

–4

if

an

entry

for

the

search

key

exists

in

the

index,

it

isdeleted

by

replacing

the

entry

in

the

index

with

thenext

search-key

value

in

the

file

(in

search-key

order).4

If

the

next

search-key

value

already

has

an

indexentry,

the

entry

is

deleted

instead

of

being

replaced.11

.

14©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionIndex

Update:

Insertion11

.

15©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Single-level

index

insertion:l

Perform

a

lookup

using

the

search-key

value

appearingin

the

record

to

be

inserted.l

Dense

indices

–

if

the

search-key

value

does

notappear

in

the

index,

insert

it.l

Sparse

indices

–

if

index

stores

an

entry

for

eachblock

of

the

file,

no

change

needs

to

be

made

to

theindex

unless

a

new

block

is

created.4

If

a

new

block

is

created,

the

first

search-key

valueappearing

in

the

new

block

is

inserted

into

theindex.n

Multilevel

insertion

and

deletion:

algorithms

are

simpleextensions

of

the

single-level

algorithmsSecondary

Indices11

.

16©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Frequently,

one

wants

to

find

all

the

records

whosevalues

in

a

certain

field

(which

is

not

the

search-key

ofthe

primary

index)

satisfy

some

condition.l

Example

1:

In

the

instructor

relation

storedsequentially

by

ID,

we

may

want

to

find

all

instructorsin

a

particular

departmentl

Example

2:

as

above,

but

where

we

want

to

find

allinstructors

with

a

specified

salary

or

with

salary

in

aspecified

range

of

valuesn

We

can

have

a

secondary

index

with

an

index

record

foreach

search-key

valueB+-Tree

Index

Files11

.

17©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionB+-tree

indices

are

an

alternative

to

indexed-sequential

files.n

Disadvantage

of

indexed-sequential

filesl

performance

degrades

as

file

grows,

since

manyoverflow

blocks

get

created.l

Periodic

reorganization

of

entire

file

is

required.n

Advantage

of

B+-tree

index

files:l

automatically

reorganizes

itself

with

small,

local,changes,

in

the

face

of

insertions

and

deletions.l

Reorganization

of

entire

file

is

not

required

to

maintainperformance.n

(Minor)

disadvantage

of

B+-trees:l

extra

insertion

and

deletion

overhead,

space

overhead.n

Advantages

of

B+-trees

outweigh

disadvantagesl

B+-trees

are

used

extensivelyExample

of

B+-Tree11

.

18©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionB+-Tree

Index

Files

(Cont.)11

.

19©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionA

B+-tree

is

a

rooted

tree

satisfying

the

following

properties:n

All

paths

from

root

to

leaf

are

of

the

same

lengthn

Each

node

that

is

not

a

root

or

a

leaf

has

betweenn/2

and

n

children.n

A

leaf

node

has

between

(n–1)/2

and

n–1

valuesn

Special

cases:l

If

the

root

is

not

a

leaf,

it

has

at

least

2

children.l

If

the

root

is

a

leaf

(that

is,

there

are

no

othernodes

in

the

tree),

it

can

have

between

0

and

(n–1)values.B+-Tree

Node

Structuren

Typical

nodel

Ki

are

the

search-key

valuesl

Pi

are

pointers

to

children

(for

non-leaf

nodes)

orpointers

to

records

or

buckets

of

records

(for

leafnodes).n

The

search-keys

in

a

node

are

orderedK1

<

K2

<

K3

<

.

.

.

<

Kn–1(Initially

assume

no

duplicate

keys,

address

duplicateslater)11

.

20©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionLeaf

Nodes

in

B+-TreesProperties

of

a

leaf

node:n

For

i

=

1,

2,

.

.

.,

n–1,

pointer

Pi

points

to

a

file

recordwith

search-key

value

Ki,n

If

Li,

Lj

are

leaf

nodes

and

i

<

j,Li’s

search-key

valuesare

less

than

or

equal

to

Lj’s

search-key

valuesn

Pn

points

to

next

leaf

node

in

search-key

order11

.

21©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionNon-Leaf

Nodes

in

B+-Treesn

Non

leaf

nodes

form

a

multi-level

sparse

index

on

the

leafnodes.

For

a

non-leaf

node

with

m

pointers:l

All

the

search-keys

in

the

subtree

to

which

P1

pointsare

less

than

K1l

For

2

i n

–

1,

all

the

search-keys

in

the

subtree

towhich

Pi

points

have

values

greater

than

or

equal

to

Ki–1and

less

than

Kil

All

the

search-keys

in

the

subtree

to

which

Pn

pointshave

values

greater

than

or

equal

to

Kn–111

.

22©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionExample

of

B+-treeB+-tree

for

instructor

file

(n

=

6)n

Leaf

nodes

must

have

between

3

and

5

values(

(n–1)/2

and

n

–1,

with

n

=

6).n

Non-leaf

nodes

other

than

root

must

have

between3

and

6

children

(

(n/2

and

n

with

n

=6).n

Root

must

have

at

least

2

children.11

.

23©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionObservations

about

B+-trees11

.

24©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Since

the

inter-node

connections

are

done

by

pointers,“logically”

close

blocks

need

not

be

“physically”

close.n

The

non-leaf

levels

of

the

B+-tree

form

a

hierarchy

ofsparse

indices.n

The

B+-tree

contains

a

relatively

small

number

of

levels4

Level

below

root

has

at

least

2*

n/2

values4

Next

level

has

at

least

2*

n/2

*

n/2

values4

..

etc.l

If

there

are

K

search-key

values

in

the

file,

the

treeheight

is

no

more

than

logn/2(K)l

thus

searches

can

be

conducted

efficiently.n

Insertions

and

deletions

to

the

main

file

can

be

handledefficiently,

as

the

index

can

be

restructured

in

logarithmictime

(as

we

shall

see).Queries

on

B+-Trees11

.

25©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Find

record

with

search-key

value

V.C=rootWhile

C

is

not

a

leaf

node

{Let

i

be

least

value

s.t.

V

Ki.If

no

such

exists,

set

C

=

last

non-null

pointer

in

Celse

set

C

=

Pi}3.

Else

{

if

(V=

Ki

)

Set

C

=

Pi

+1}Let

i

be

least

value

s.t.

Ki

=

VIf

there

is

such

a

value

i,

follow

pointer

Pirecord.Else

no

record

with

search-key

value

k

exists.to

the

desiredHandling

Duplicates11

.

26©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

With

duplicate

search

keysl

In

both

leaf

and

internal

nodes,4

we

cannot

guarantee

that

K1

<

K2

<

K3

<

.

.

.

<

Kn–14

but

can

guarantee

K1

K2

K3

.

.

.Kn–1l

Search-keys

in

the

subtree

to

which

Pi

points4

are

Ki,,

but

not

necessarily

<

Ki,4

To

see

why,

suppose

same

search

key

value

V

ispresent

in

two

leaf

node

Li

and

Li+1. Then

in

parentnode

Ki

must

be

equal

to

VHandling

Duplicates11

.

27©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

We

modify

find

procedure

as

followsl

traverse

Pi

even

if

V

=

Kil

As

soon

as

we

reach

a

leaf

node

C

check

ifC

has

only

search

key

values

less

than

V4if

so

set

C

=

right

sibling

of

C

beforechecking

whether

C

contains

Vn

Procedure

printAlll

uses

modified

find

procedure

to

find

firstoccurrence

of

Vl

Traverse

through

consecutive

leaves

to

find

alloccurrences

of

V**

Errata

note:

modified

find

procedure

missing

in

first

printing

of

6th

editionQueries

on B+-Trees

(Cont.)11

.

28©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

If

there

are

K

search-key

values

in

the

file,

the

height

of

then/2tree

is

no

more

than

log

(K)

.n

A

node

is

generally

the

same

size

as

a

disk

block,

typically

4kilobytesl

and

n

is

typically

around

100

(40

bytes

per

index

entry).n

With

1

million

search

key

values

and

n

=

100l

at

most

log50(1,000,000)

=

4

nodes

are

accessed

in

alookup.n

Contrast

this

with

a

balanced

binary

tree

with

1

million

searchkey

values

—

around

20

nodes

are

accessed

in

a

lookupl

above

difference

is

significant

since

every

node

access

mayneed

a

disk

I/O,

costing

around

20

millisecondsUpdates

on

B+-Trees:

Insertion11

.

29©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEdition

Find

the

leaf

node

in

which

the

search-key

value

wouldappearIf

the

search-key

value

is

already

present

in

the

leaf

nodeAdd

record

to

the

fileIf

necessary

add

a

pointer

to

the

bucket.If

the

search-key

value

is

not

present,

then

add

the

record

to

the

main

file

(and

create

a

bucket

ifnecessary)

If

there

is

room

in

the

leaf

node,

insert

(key-value,pointer)

pair

in

the

leaf

node

Otherwise,

split

the

node

(along

with

the

new

(key-value,

pointer)

entry)

as

discussed

in

the

next

slide.(Cont.)n

Splitting

a

leaf

node:l

take

the

n

(search-key

value,

pointer)

pairs

(including

the

onebeing

inserted)

in

sorted

order.

Place

the

first

n/2

in

theoriginal

node,

and

the

rest

in

a

new

node.l

let

the

new

node

be

p,

and

let

k

be

the

least

key

value

in

p.Insert

(k,p)

in

the

parent

of

the

node

being

split.l

If

the

parent

is

full,

split

it

and

propagate

the

split

furthen

Splitting

of

nodes

proceeds

upwards

till

a

node

that

is

not

full

isfound.l

In

the

worst

case

the

root

node

may

be

split

increasing

theheight

of

the

tree

by

1.Result

of

splitting

node

containing

Brandt,

Califieri

and

Crick

on

insertingAdamsNext

step:

insert

entry

with

(Califieri,pointer-to-new-node)

into

parent11

.

30©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionB+-TreeInsertionB+-Tree

before

and

after

insertion

of

“Adams”11

.

31©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionB+-TreeInsertionB+-Tree

before

and

after

insertion

of

“Lamport”11

.

32©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Splitting

a

non-leaf

node:

when

inserting

(k,p)

into

an

already

fulinternal

node

Nl

Copy

N

to

an

in-memory

area

M

with

space

for

n+1

pointersand

n

keysl

Insert

(k,p)

into

Ml

Copy

P1,K1,

…,

K

n/2

-1,P

n/2

from

M

back

into

node

Nl

Copy

P

+1,Kn/2

n/2+1,…,Kn,Pn+1

from

M

into

newly

allocatednode

N’n/2l

Insert

(K

,N’)

into

parent

Nn

Read

pseudocode

in

book!CrickInsertion

in

B+-Trees

(Cont.)AdamsBrandtCalifieriCrickAdams

BrandtCalifieri11

.

33©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionExamples

of

B+-Tree

Deletionn

Deleting

“Srinivasan”

causes

merging

of

under-full

leavesBefore

and

after

deleting

“Srinivasan”11

.

34©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionExamples

of

B+-Tree

Deletion

(Cont.)Deletion

of

“Singh”

and

“Wu”

from

result

of

previousexamplen

Leaf

containing

Singh

and

Wu

became

underfull,

and

borrowed

avalue

Kim

from

its

left

siblingn

Search-key

value

in

the

parent

changes

as

a

result11

.

35©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionExample

of

B+-tree

Deletion

(Cont.)Before

and

after

deletion

of

“Gold”

from

earlier

examplen

Node

with

Gold

and

Katz

became

underfull,

and

was

merged

with

itssiblingn

Parent

node

becomes

underfull,

and

is

merged

with

its

siblingl

Value

separating

two

nodes

(at

the

parent)

is

pulled

down

whenmerging11

.

36©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionUpdates

on

B+-Trees:

Deletion11

.

37©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Find

the

record

to

be

deleted,

and

remove

it

from

the

main

fileand

from

the

bucket

(if

present)n

Remove

(search-key

value,

pointer)

from

the

leaf

node

if

there

isno

bucket

or

if

the

bucket

has

become

emptyn

If

the

node

has

too

few

entries

due

to

the

removal,

and

theentries

in

the

node

and

a

sibling

fit

into

a

single

node,

thenmerge

siblings:l

Insert

all

the

search-key

values

in

the

two

nodes

into

a

singlnode

(the

one

on

the

left),

and

delete

the

other

node.l

Delete

the

pair

(Ki–1,

Pi),

where

Pi

is

the

pointer

to

thedeleted

node,

from

its

parent,

recursively

using

the

aboveprocedure.Updates

on

B+-Trees:

Deletion11

.

38©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Otherwise,

if

the

node

has

too

few

entries

due

to

the

removal,

but

the

entries

in

the

node

and

a

sibling

do

not

fit

into

a

singlenode,

then

redistribute

pointers:l

Redistribute

the

pointers

between

the

node

and

a

sibling

suchthat

both

have

more

than

the

minimum

number

of

entries.l

Update

the

corresponding

search-key

value

in

the

parent

ofthe

node.n

The

node

deletions

may

cascade

upwardstill

a

node

which

hasn/2

or

more

pointers

is

found.n

If

the

root

node

has

only

one

pointer

after

deletion,

it

is

deletedand

the

sole

child

becomes

the

root.Non-Unique

Search

Keys11

.

39©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Alternatives

to

scheme

described

earlierl

Buckets

on

separate

block

(bad

idea)l

List

of

tuple

pointers

with

each

key4

Extra

code

to

handle

long

lists4

Deletion

of

a

tuple

can

be

expensive

if

there

are

manyduplicates

on

search

key

(why?)4

Low

space

overhead,

no

extra

cost

for

queriesl

Make

search

key

unique

by

adding

a

record-identifier4

Extra

storage

overhead

for

keys4

Simpler

code

for

insertion/deletion4

Widely

usedB+-Tree

File

Organization11

.

40©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Index

file

degradation

problem

is

solved

by

using

B+-Tree

indices.n

Data

file

degradation

problem

is

solved

by

using

B+-Tree

FileOrganization.n

The

leaf

nodes

in

a

B+-tree

file

organization

store

records,

insteof

pointers.n

Leaf

nodes

are

still

required

to

be

half

fulll

Since

records

are

larger

than

pointers,

the

maximum

number

of

records

that

can

be

stored

in

a

leaf

node

is

less

than

thenumber

of

pointers

in

a

nonleaf

node.n

Insertion

and

deletion

are

handled

in

the

same

way

as

insertionand

deletion

of

entries

in

a

B+-tree

index.B+-Tree

File

Organization

(Cont.)Example

of

B+-tree

File

Organizationn

Good

space

utilization

important

since

records

use

more

spacethan

pointers.n

To

improve

space

utilization,

involve

more

sibling

nodes

inredistribution

during

splits

and

mergesl

Involving

2

siblings

in

redistribution

(to

avoid

split

/

mergewhere

possible)

results

in

each

node

having

at

leastentries11

.

41©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionOther

Issues

in

Indexing11

.

42©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Record

relocation

and

secondary

indicesl

If

a

record

moves,

all

secondary

indices

that

store

recordpointers

have

to

be

updatedl

Node

splits

in

B+-tree

file

organizations

become

veryexpensivel

Solution:

use

primary-index

search

key

instead

of

recordpointer

in

secondary

index4

Extra

traversal

of

primary

index

to

locate

record–

Higher

cost

for

queries,

but

node

splits

are

cheap4

Add

record-id

if

primary-index

search

key

is

non-uniqueIndexing

Strings11

.

43©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Variable

length

strings

as

keysl

Variable

fanoutl

Use

space

utilization

as

criterion

for

splitting,

notnumber

of

pointersn

Prefix

compressionl

Key

values

at

internal

nodes

can

be

prefixes

of

full

key4

Keep

enough

characters

to

distinguish

entries

in

thesubtrees

separated

by

the

key

value–

E.g.“Silas”

and

“Silberschatz”

can

beseparated

by

“Silb”l

Keys

in

leaf

node

can

be

compressed

by

sharingcommon

prefixesBulk

Loading

and

Bottom-Up

Build11

.

44©Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Inserting

entries

one-at-a-time

into

a

B+-tree

requiresl

assuming

leaf

level

does

not

fit

in

memory1

IO

per

el

can

be

very

inefficient

for

loading

a

large

number

of

entries

attime

(bulk

loading)n

Efficient

alternative

1:l

sort

entries

first

(using

efficient

external-memory

sort

algorithdiscussed

later

in

Section

12.4)l

insert

in

sorted

order4

insertion

will

go

to

existing

page

(or

cause

a

split)4

much

improved

IO

performance,

but

most

leaf

nodes

half

fulln

Efficient

alternative

2:

Bottom-up

B+-tree

constructionl

As

before

sort

entriesl

And

then

create

tree

layer-by-layer,

starting

with

leaf

level4

details

as

an

exercisel

Implemented

as

part

of

bulk-load

utility

by

most

database

systemsB-Tree

Index

Filesn

Similar

to

B+-tree,

but

B-tree

allows

search-key

values

toappear

only

once;

eliminates

redundant

storage

of

searchkeys.n

Search

keys

in

nonleaf

nodes

a