程序设计与算法基础课件

程序设计与算法基础(6)1潘爱民2006/10/30Outline2Hash

tablesBloom

filterInverted

indexSearching

problem

again3For

a

linked

list,

->O(n)For

a

sorted

array,

->

O(logn)Can

we

expect

O(1)?

which

meansRegardless

of

the

number

of

elements

beingsearched,

the

run

time

is

always

the

sameGiven

a

key,

the

position

in

the

table

can

beaccessed

directlyOperations

on

hash

tables4Collection

of

pairs(key,

element),

here

key

maybe

a

string,number,record,

etc.Pairs

have

different

keysOperationsGet(theKey)Delete(theKey)Insert(theKey,

theElement)Ideal

Hashing5Uses

a

1D

array

(or

table)

table[0…m-1].Each

position

of

this

array

is

a

bucketA

bucket

can

normally

hold

only

one

pairUses

a

hash

function

h

that

converts

eachkey

k

into

an

index

in

the

range

[0,

m-1]h(k)

is

the

home

bucket

for

key

kEvery

pair

(key,

element)

is

stored

in

its

homebucket

table[h[key]][6]6[7]Ideal

Hashing

ExamplePairs

are:

(22,a),

(33,c),

(3,d),

(73,e),(85,f)Hash

table

is

table[0…7],

m

=

8Hash

function

ish(key)

=

key/11Pairs

are

stored

in

table

as

below(3,d)(22,a)(33,c)(73,e)(85,f)[0]

[1]

[2]

[3]

[4]

[5]Get,

Insert,

and

Delete

take

O(1)

timeWhat

Can

Go

Wrong?7[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]Where

does

(26,g)

go?Keys

that

have

the

same

home

bucket

aresynonyms22

and

26

are

synonyms

with

respect

to

the

hashfunctionthat

is

in

use.The

home

bucket

for

(26,g)

is

already

occupied.(3,d)(22,a)(33,c)(73,e)(85,f)What

Can

Go

Wrong?8A

collision

occurs

when

the

home

bucket

fora

new

pair

is

occupied

by

a

pair

with

adifferent

keyAn

overflow

occurs

when

there

is

no

space

inthe

home

bucket

for

the

new

pairWhen

a

bucket

can

hold

only

one

pair,collisions

and

overflows

occur

togetherNeed

a

method

to

handle

overflows(3,d)(22,a)(33,c)(73,e)(85,f)Hash

Table

Issues9Choice

of

hash

functionsCollision

resolutionSize

of

hash

tableThe

size

of

bucket

&

number

of

bucketsHash

functions10Definition:A

hash

function

transforms

a

key

K

into

an

index

in

thetable

used

for

storing

items

of

the

same

type

as

KIf

hash

function

h

transforms

different

keys

into

differentnumbers,

it

is

called

aperfect

hash

functionTherefore,

a

hash

function

is

a

mapping

from

n

itemsto

m

positionsTotal

number

of

possible

mappings

is

mnIf

n

m,

the

number

of

perfect

hash

functions

is

m!/(m-n)!Hash

Functions11Two

partsConvert

a

key

into

an

integer

in

case

the

key

isnot

anintegerh(k)Map

an

integer

into

a

home

bucketf(k)

is

an

integer

in

the

range

[0,

m-1],

where

m

is

thenumber

of

buckets

in

the

tableString

To

Non-negative

Integer12Each

character

is1

byte

longAn

int

is

4bytesA

two-character

string

s

may

be

converted

into

aunique

4

byte

non-negative

int

using

the

code:int

answer

=

s.at(0);answer

=

(answer

<<

8)

+s.at(1);Strings

that

are

longer

than

3

characters

do

not

havea

unique

non-negative

int

representationString

To

Nonnegative

Integerunsigned

long

operator()(const

stringtheKey){//

Convert

theKey

to

a

nonnegative

integer.unsigned

long

hashValue

=0;int

length

=

(int)

theKey.length();for

(int

i

=

0;

i

<

length;

i++)hashValue

=

5

*

hashValue+

theKey.at(i);return

hashValue;}13Map

into

a

homebucket14Most

common

method

is

bydivisionhomeBucket

=

h(theKey)

%

divisor;divisor

equals

the

number

of

buckets

m0

homeBucket

<

divisor

=

m[0]

[1]

[2]

[3]

[4]

[5]

[6][7](3,d)(22,a)(33,c)(73,e)(85,f)Uniform

Hash

Function15Let

keySpacebe

the

set

of

all

possible

keysA

uniform

hash

function

maps

the

keys

inkeySpace

into

buckets

such

thatapproximately

the

same

number

of

keys

getmapped

into

eachbucket[0]

[1][2]

[3]

[4]

[5]

[6][7](3,d)(22,a)(33,c)(73,e)(85,f)Uniform

Hash

Function16[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]Equivalently,

the

probability

that

a

randomlyselected

key

has

bucket

i

as

its

home

bucket

is1/m,0

i<mA

uniform

hash

function

minimizes

thelikelihood

of

an

overflow

when

keys

areselected

at

random(3,d)(22,a)(33,c)(73,e)(85,f)Hashing

By

Division17keySpace

=

all

intsFor

every

m,

the

number

ofints

that

getmapped

(hashed)

into

bucket

i

isapproximately232/mTherefore,

the

division

method

results

in

auniform

hash

function

whenkeySpace

=

all

intsIn

practice,

keys

tend

to

be

correlatedSo,

the

choice

of

the

divisor

m

affects

thedistribution

of

home

bucketsSelecting

The

Divisor18Because

of

this

correlation,

applications

tendtohave

a

bias

towards

keys

that

map

into

oddintegers

(or

into

even

ones)When

the

divisor

is

an

even

number,

oddintegers

hash

into

odd

home

buckets

andevenintegers

into

even

home

buckets20%14

=

6,

30%14

=

2,

8%14

=

815%14

=

1,

3%14

=

3,

23%14

=

9The

bias

in

the

keys

results

in

a

biastowardeither

the

odd

or

even

home

bucketsSelecting

The

Divisor19When

the

divisor

is

an

odd

number,

odd

(even)integers

may

hash

into

anyhome20%15

=

5,

30%15

=

0,

8%15

=

815%15

=

0,

3%15

=

3,

23%15

=

8The

bias

in

the

keys

does

not

result

in

a

biastoward

either

the

odd

or

even

home

bucketsBetter

chance

of

uniformly

distributed

homebucketsSo

do

not

use

an

evendivisorSelecting

The

Divisor20Similar

biased

distribution

of

home

bucketsisseen,

in

practice,

when

the

divisor

is

a

multipleof

prime

numbers

such

as

3,

5,

7,

…The

effect

of

each

prime

divisor

p

of

mdecreases

as

p

gets

largerIdeally,

choosem

so

that

it

is

a

primenumberAlternatively,

choosem

so

that

it

has

no

primefactor

smaller

than

20Hashing

by

folding21The

key

is

divided

into

several

parts,

andthese

parts

are

combined

or

folded

togetherShift

foldingUsing

a

simple

operation

such

as

addition

to

combinethem

in

a

certain

wayFor

example,

the

social

security

number

(SSN),123-45-6789(123

+

456

+

789)%m

(m=1000)Boundary

foldingThe

pieces

of

the

keys

are

folded

on

the

bordersbetween

different

parts,

for

example(123+654+789)%m

(m=1000)About

folding22Simple

and

fast,

bit

pattern

can

be

usedinstead

of

numerical

valuesIn

the

case

ofstringsXor’ing

the

characters

together,

and

usingtheresult

for

theaddressXor’ing

the

chunks

of

strings

rather

than

singlecharacters.

The

length

of

a

chunk

is

equal

to

thenumber

of

bytes

in

an

integerTypically,

the

result

of

folding

processing

aredivided

modulo

mHashing

by

a

Mid-squarefunction23The

key

issquared

and

the

middle

or

mid

part

of

theresult

is

used

as

the

hashvalueEntire

key

participates

in

generating

the

hash

value,

so

abetter

chance

that

the

different

values

are

generated

fordifferent

keysIn

practice,

it

is

more

efficient

to

choose

a

power

of

2

forthe

size

of

the

table,

m,

and

extract

the

mid

part

of

the

bitrepresentation

of

the

square

of

a

key,

just

using

a

maskand

a

shiftoperationFor

example,

31212=100101001010000101100001,the

mid

part

101000010

=

322Hashing

by

extraction24Only

a

part

of

the

key

is

used

to

compute

theaddressIf

the

part

is

distributed

uniformly,

it

can

besufficient

for

hashing

(provided

the

omitted

portiondistinguishes

the

keys

only

in

an

insignificant

way)For

example,

in

the

student

ID,

some

digits

aresafely

omitted

in

a

hash

functionISBN

code

issimilarHashing

by

radixtransformation25The

key

is

transformed

into

another

numberbaseFor

example,

K

is

the

decimal

number345,thenits

value

in

base

9

is

423(9)Then

it

is

divided

modulo

m

in

original

base,

theresulting

number

is

used

as

the

hash

valueIf

m

=

100,

345(10)

and

245(10)

are

not

hashed

tothe

same

value,

but345(10)

and

264(10)

will

behashed

to

a

same

value,

23Hashing

by

cryptographichash

algorithms26Strong

hash

algorithmsA

change

of

any

bit

in

the

input

will

cause

thechange

of

any

bit

in

the

output

with

0.5

probabilityapproximatelyThe

encryption

algorithm

has

similar

featureUsing

cryptographic

algorithms

to

hash

akeyFor

example,

compute

the

MD5(key)

orSHA1(key)or

encrypt

the

key

with

a

fixed

encryptionkey,DESk(key)Then

divided

modulo

mCollision

resolution27AvoidcollisionIncreasing

the

table

size

may

lead

to

better

hashing,

butsometimesnotThe

two

factors

–

hash

function

and

table

size

–

mayminimize

the

number

of

collisions,

but

they

can

notcompletely

eliminate

them(if

the

size

of

key

space

is

larger

than

the

tablesize)Some

strategiesOpen

addressingChainingBucket

addressingCollision

resolution

byopening

addressing28A

collision

occurs

when

the

home

bucket

for

anew

pair

(key,

element)

is

occupiedWe

may

handle

collisions

by:Search

the

hash

table

in

some

systematic

fashion

fora

bucket

that

is

not

occupied.Linear

probingQuadratic

probingRandom

probingEliminate

overflows

by

permitting

each

bucket

tokeep

a

list

of

all

pairs

for

which

it

is

the

homebucketDynamic

arraylinked

listOpening

addressing29If

the

position

h(K)

is

occupied,

then

the

positions

inthe

probing

sequencenorm(h(K)+p(1)),

norm(h(K)+p(2)),

…,

norm(h(K)+p(m))are

trieduntileither

an

available

cell

is

foundor

the

same

positions

are

tried

repeatedlyor

the

table

is

fullIn

the

probing

sequence,Function

p

is

probing

functioni

is

aprobenorm

is

a

normalization

function,

(division

modulo

to

thesize

of

thetable)Linear

probing30In

the

open

addressingp(i)

=

c*i,so

if

c

=1,

then

the

position

to

be

tried

is

(h(K)

+

i)In

linear

probing,Insertion:

the

position

to

store

a

key

is

found

bysequentially

searching

all

positions

starting

from

theposition

calculated

by

the

hash

function

until

an

emptycellis

foundTendency

to

create

clusters

in

the

table,

the

empty

cellsfollowing

clusters

have

a

much

greater

chance

to

be

filledthan

other

positionsLinear

Probing

–

Get

AndInsert31divisor

=

m

(number

of

buckets)

=

17Home

bucket

=

key

%

170

4

81216Insert

pairs

whose

keys

are

6,

12,

34,

29,

28,11,23,7,0,33,30,45340456237281229113033Quadratic

probing32In

the

open

addressingIn

general,

p(i)

=

c2*i2+c1*i

,

for

example,p(i)

=

(-1)i-1((i+1)/2)2,

so

the

position

to

be

tried

ish(K),

h(K)

+1,

h(K)

-1,

h(K)

+

4,

h(K)

-4,

…,h(K)+(m-1)2/4,

h(K)

–(m-1)2/4The

experience

value

of

m

(table

size)

is

a

prime

in

theform

of

4j+1Question:Why

not

usep(i)

=

i2,

0

i<m(i2-j2)=(i+j)(i-j)The

effect

of

clustering

is

better

than

linear

probingSecondary

cluster

for

the

keys

hashed

to

the

same

locationRandom

probing33p

function

is

defined

as

a

pseudo

randomnumber

generatorArequirementIn

order

to

find

the

probing

sequence,

the

randomnumber

generator

should

be

initialized

tothesame

seed

for

the

same

keyAvoid

secondary

clustersThe

same

probing

sequence

for

a

keyDifferent

probing

sequences

for

different

keys

withthe

same

hashvalueDouble

hashingp

function

is

defined

with

another

hash

function,hp(K)p(i)

=

i*hp(K)The

probing

sequence

ish(K),

h(K)

+hp(K),

h(K)

+2hp(K),

h(K)

+

3hp(K),

…,h(K)+(m-1)hp(K)The

probing

sequence

will

depend

on

the

choice

of

hashfunction

hp(K)The

hash

functionhp(K)

can

be

defined

with

theoriginal

hash

function

h(K),

for

example,hp(K)

=

i*h(K)+1,

then

the

probing

sequence

ish(K)

+i*(i*h(K)+1)=(i2+1)h(K)+iSecondary

clusters34Performance

of

openingaddressing35Successful

searches

vs.

unsuccessful

searches[The

Art

of

Computer

Programming,

Volume

3]Linear

probingQuadraticsearchDouble

hashingSuccessfulsearches[1+1/(1-LF)]/21-ln(1-LF)-LF/2-ln(1-LF)/LFUnsuccessfulsearches[1+1/(1-LF)2]/21/(1-LF)-LF-ln(1-LF)1/(1-LF)LF

=n/m,

load

factor

=

(number

of

elements

in

the

table)/table

sizePerformance

Of

Linear

Probing36Worst-case

Get/Insert

time

is

(n),

where

n

is

the

number

of

keys

in

thetableThis

happens

when

all

pairs

are

in

the

same

clusterExpected

PerformanceSn

=

expected

number

of

buckets

examined

in

a

successfulsearchUn

=

expected

number

of

buckets

examined

in

a

unsuccessfulsearch0

4

8

1216340456237281229113033Expected

Performance37Sn

~

[1+1/(1-LF)]/2Un

~

[1+1/(1-LF)2]/2Note

that0

LF

1LF

0.65isrecommended.LFSnUn0.51.52.50.651.94.60.752.58.50.905.550.5Linear

Probing

–

Delete380

4

81216340456237281229113033Delete(0)048121634456237281229113033Search

cluster

for

pair

(if

any)

to

fill

vacatedbucket0

4

8

12

1634456237281229113033Linear

Probing

–

Delete(34)39Search

cluster

for

pair

(if

any)

to

fill

vacatedbucket0

4

8

12

16045623728122911303304812160456237281229113033048121634045623728122911303304812160456237281229113033Linear

Probing

–

Delete(29)0

4

8

1240163404562372812291130330

4

8

12Search

cluster

for

pair

(if

any)

to

fill

vacatedbucket1634045623728121130330

48121634045623728121130330481216340456237281211303304812163406237281211304533Hash

Table

Design41Performance

requirements

are

given,

determinemaximum

permissible

load

factorWe

want

a

successful

search

to

make

no

more

than10

compares

(expected)Sn

~

½(1

+

1/(1

–

LF))LF

18/19We

want

an

unsuccessful

search

to

make

no

morethan

13

compares(expected)Un

~

½(1

+

1/(1

–

LF)2)LF

4/5So

LF

min{18/19,

4/5}

=

4/5Hash

Table

Design42Dynamic

resizing

of

tableWhenever

load

factor

exceeds

threshold

(4/5

in

ourexample),

rehash

into

a

table

of

approximately

twicethecurrent

sizeFixed

table

sizeKnow

maximum

number

of

pairsNo

more

than

1000

pairsLF

4/5

=>m

5/4*1000

=1250.Pick

m

(equal

to

divisor)

to

be

a

prime

number

or

an

oddnumber

with

no

prime

divisors

smaller

than

20Collision

resolution:

chaining43Each

bucket

keeps

a

linear

list

of

all

pairs

forwhich

it

is

the

home

bucketNever

overflow

if

the

capacity

of

the

linear

list

isunlimitedThe

linear

list

may

or

may

not

be

sorted

by

key.The

linear

list

may

be

an

array

linear

list

or

a

chainPerformanceIncreasing

the

length

of

the

lists

can

degraderetrieval

performanceRequire

additional

space

for

pointersSorted

ChainsPut

in

pairswhose

keys

are6,12,34,29,28,11,23,7,0,33,30,45Home

bucket=key

%17.[0][4][8][12][16]12634292811237033304544Expected

Performance45Notethat

LF

0.Expected

chain

length

is

LF.Sn

~

1

+

LF/2

(in

the

case

of

unsortedlist)Un

~

LFCoalesced

hashing

(coalescedchaining)Combine

linear

probing

and

chainingl

h(K)

=K%17l

Insert

pairs

whose

keys

are6,

12,

34,

29,

28,

11,23,

7,

00

4

8

12

1634

0

6

23

7

28

12

29

11Alternatively,

the

colliding

key

can

be

put

inan

overflow

area

(called

a

cellar)46Bucket

addressing47Associate

a

bucket

with

each

address,

and

abucket

is

a

block

of

space

enough

to

storemultiple

itemsCollision

is

not

totally

avoided,

if

a

bucket

isfull,

thenA

new

item

hashed

to

the

bucket

can

be

stored

inthe

next

bucket,

just

as

does

in

the

openaddressing

approachThe

new

item

can

also

be

stored

in

anoverflowarea.

The

bucket

will

be

marked

with

a

flagindicating

it

has

additional

items

to

be

searchedPerfect

hash

functions48Perfect

hash

functions

or

ideal

hash

functionsIt

hashes

a

key

to

its

proper

position,

and

no

collisionsoccurAn

assumption

is

that

the

key

set

is

knownIf

the

number

of

cells

in

the

table

is

equal

to

the

number

ofdata

items,

it

is

called

a

minimal

perfect

hash

functionso

no

space

is

wastedExamplesReserved

words

used

by

assemblers,

compilers,

filesonunerasable

optical

disks,

dictionaries,

…It

is

not

easy

to

obtain

a

perfect

hash

functionCichelli’s

method

to

construct

aminimal

perfect

hash

function49Developed

by

Richard

J.

CichelliUsed

to

hash

a

relatively

small

number

ofreserved

wordsThe

function

is

of

the

formh(word)

=

(length(word)

+

g(firstletter(word))+

g(lastletter(word)))

mod

mwhere

g

is

the

function

to

be

constructedCichelli’s

algorithm50Choose

a

value

for

MaxCompute

the

number

of

occurrences

of

each

firstand

last

letter

in

the

set

of

all

wordsOrder

all

words

in

accordance

to

the

frequency

ofoccurrence

of

the

first

and

the

last

lettersExamples:

Calliope,

Clio,

Erato,

Euterpe,Melpomene,

Polyhymnia,

Terpsichore,

Thalia,Urania

=>

E(6),

A(3),

C(2),

O(2),

T(2),

M(1),

P(1),

U(1)Euterpe,

Calliope,

Erato,

Terpsichore,

Melpomene,Thalia,

Clio,

Polyhymnia,

UraniaCichelli’s

algorithm

(cont.)Search(wordList)if

wordList

is

emptyhalt;word

=

first

word

from

wordList;wordList

=

wordList

with

the

first

word

detached;if

the

first

and

the

last

letters

of

word

are

assigned

g-valuestry(word,

-1,

-1)

//

-1

signifies

‘value

already

assigned’ifsuccessSearch(wordList)put

word

at

the

beginning

of

wordList

and

detach

itshashvalue;else

if

neigher

the

first

nor

the

last

letters

has

a

g-valuefor

each

n,m

in

{0,

…,

Max)try(word,

n,

m);ifsuccessSearch(wordList)put

word

at

the

beginning

of

wordList

and

detach

itshashvalue;else

if

either

the

first

or

the

last

letter

has

ag-valuefor

each

n

in

{0,

…,

Max)try(word,

-1,

n);ifsuccess51Cichelli’s

algorithm

(cont.)try(word,

firstLetterValue,

lastLetterValue)if

h(word)

has

not

been

claimedreserve

h(word);if

not

-1(i.e.,

not

reserved)assign

firstLetterValue

and/or

lastLetterValueasg-values

offirstletter(word)

and/or

lastletter(word)return

successreturn

failure52A

invocations

of

the

searching

procedurereserved

hash

valuesEuterpe

E=0

h=7TerpsichoreCalliope

C=0

h=8Erato

O=0

h=5T=0h=2Melpomene

M=0Thalia

A=0Clioh=0h=6h=4h=1h=6*h=7*h=8*h=0*h=1*h=2

*h=3h=6*{7}{78}{578}{2578}{02578}{025678}{0245678}{01245678}{01245678}{01245678}{01245678}{01245678}{01245678}{0245678}{02345678}{02345678}h=7*h=8*h=0*Polyhymnia

P=0Urania

U=0Urania

U=1Urania

U=2Urania

U=3Urania

U=4Polyhymnia

P=1Polyhymnia

P=2Urania

U=0Urania

U=1Urania

U=2Urania

U=3Urania

U=4h=1{02345678}{02345678}{02345678}{012345678}53About

cichelli’s

algorithm54A

brute-force

search

for

g-function,

so

thesearchprocess

is

exponentialIt

is

not

applicable

to

a

large

number

of

wordsIt

does

not

guarantee

that

a

perfect

hash

function

can

befoundExtensions(1)

The

second

to

last

letters

in

the

word

are

involved

in

thehash

functions(2)

h(word)

=

length(word)

+

g1(firstletter(word))

+…+glength(word)(lastletter(word))(3)

h(word)

=

bucketgr(word)

+

hgr(word)(word)FHCD

algorithm55Search

for

a

minimal

perfect

hash

function

of

theformh(word)

=

h0(word)+

g(h1(word))+g(h2(word))h0:

key

space

->[0,m)h1:

key

space

->[0,

r)h2:

key

space

->[r,2r)Steps:Mapping

(dependency

graph):

between

h1

to

h2

for

eachwordOrdering:

first

determine

the

node

with

more

linksSearching:

assign

hash

values

to

keys

by

choosingappropriate

g-value

for

each

vertexFor

each

vertex,

eitherg(h1(word))

or

g(h2(word))

is

knownExtensible

hashing000110110001100110001011001111011111000110001011221b00b01b1000110110001100110001011001101100010112h(k)=11001

h(k)=000012

222b00b01b101101111100110012b1100011000011001101100010113322b000b01b101101111100110012b110000010100111001011101115600110001013b001An

example

of

hash

functionIn

distributed

environments,

how

to

partition

alarge

number

of

jobs

(or

records)

into

acluster

ofmachineskeyv=h(key)57Linear

hashingNo

index

is

neededThe

bucket

is

split

ifnecessaryAt

each

level

of

splitting,

linear

hashing

maintaintwo

hash

functions,hlevel

and

hlevel+1,

suchthathlevel

=

K

mode(TSize*2level)000101011000110000100111100111010011101158STL

hash_map59Simply

uses

a

divisor

that

is

an

odd

numberThis

simplifies

implementation

because

wemust

be

able

to

resize

the

hash

table

as

morepairs

are

put

into

the

dictionaryArray

doubling,

for

example,

requires

you

to

gofrom

a

1D

array

table

whose

length

is

m

(which

isodd)

to

an

array

whose

length

is

2m+1

(which

isalsoodd)About

hash

tables60Perfect

hash

functions

(n

m)Uniform

hash

functions

(n

≥

m)Performance

requirementsHow

to

deal

with

collisionsHow

to

deal

with

overflows

if

the

size

ofbuckets

is

fixedBloom

Filters

–

an

introduction61Differential

FilesSimple

large

databaseFile

of

records

residing

on

diskSingle

keyIndex

to

recordsOperationsRetrieveUpdateInsert

a

new

recordMake

changes

to

an

existingrecordDelete

a

recordNaïve

Mode

Of

OperationProblemsIndex

and

File

change

with

timeRecovery

=>Copy

Master

File

(MF)

from

backupCopy

Master

Index

(MI)

from

backupProcess

all

transactions

since

last

backupRecovery

time

depends

on

MF

&

MIsize

+

#

transactions

since

lastbackupKeyIndexFile62Differential

FileMake

no

changes

to

master

fileAlter

index

and

write

updated

recordKeyIndexFileDFto

a

new

file

calleddifferential

fileAdvantage63DF

is

smaller

than

File

and

so

may

bebacked

up

more

frequentlyIndex

needs

to

be

backed

upwhenever

DF

is.

So,

index

should

beno

larger

than

DFRecovery

time

is

reducedDifferential

File

OperationKeyIndexFileDFDisadvantage64Eventually

DF

becomes

large

and

canno

longer

be

backed

up

with

desiredfrequencyMust

integrate

File

and

DF

nowFollowing

integration,

DF

is

emptyDifferential

File

OperationKeyIndexFileDFLarge

Index65Index

cannot

be

backed

up

asfrequently

as

desiredTime

to

recover

current

state

of

index

&DF

isexcessiveUse

a

differential

indexMake

no

changes

to

IndexDI

is

an

index

to

all

deleted

records

andupdated

records

in

DFDifferential

File

&

Index

OperationPerformance

hitMost

queries

search

both

DI

andIndexIncrea