mysql dba课程及文件07btree仅供网络培训学员使用

内部注意

MySQL数据库培训性能优化B+树索引

Topics 违者

DataStructure&Algorithms

B+TreeIndexinMySQL

HowtouseB+Treeindex

Multi-RangeRead（MRR）

Reference

DataStructure&Alg 违者

BinarySearch

BinarySearchTree

BalancedBinaryTree

B+Tree

BinarySearch

违者

searchasortedarray

lookattheelementinthemiddle

Ifthekeyisequaltothat,thesearchisfinished.

Ifthekeyislessthanthemiddleelement,doabinarysearchonthefirsthalf.

Ifit'sgreater,doabinarysearchofthesecondhalf.

BinarySearch(A[0..N-1],value,low,high){if(high<low)

return-1//notfound

mid=low+(high-low)/2if(A[mid]>value)

returnBinarySearch(A,value,low,mid-1)elseif(A[mid]<value)

returnBinarySearch(A,value,mid+1,high)

else

returnmid//found

}

Usingbinarysearchtofindvalue48inarray（5、

、、、、、、、、）

SequentialSearchaveragecost：

(1+2+3+4+5+6+7+8+9+10)/10=5.5

BinarySearchaveragecost:

(4+3+2+4+3+1+4+3+2+3)/10=2.9

BinarySearchTree(BS 违者

Feature：

Theleftsubtreeofanodecontainsonlynodeswithkeyslessthanthenode'skey.

Therightsubtreeofanodecontainsonlynodeswithkeysgreaterthanthenode'skey.

Boththeleftandrightsubtreesmustalsobebinarysearchtrees.

BinarySearchTree 违者

BalancedBinaryTree

违者

Definition

abinarytree

theheightofthetwosub-treesofeverynodeneverdifferbymorethan1

B+TREE

违者

TheprimaryvalueofaB+treeisinstoringdataforefficientretrievalinablock-orientedstoragecontext—inparticular,filesystems.

IncontrasttoaB-tree,“allrecords”arestoredattheleaflevelofthetree;onlykeysarestoredininteriornodes.

B+treeshaveveryhighfanout(typicallyontheorderof100ormore),whichreducesthenumberofI/Ooperationsrequiredtofindanelementinthetree.

B+treeheight：2Recordsperpage：4Fanout：5

+Treeinsert 违者

LeafPage

Full

IndexPage

Full

Action

No

No

cetherecordinsortedpositionintheappropriateleafpage

Yes

No

Splittheleafpage

ceMiddleKeyintheindexpageinsortedorder.

Leftleafpagecontainsrecordswithkeysbelowthemiddlekey.

Rightleafpagecontainsrecordswithkeysequaltoorgreaterthanthemiddlekey.

Yes

Yes

Splittheleafpage.

Recordswithkeys<middlekeygototheleftleafpage.

Recordswithkeys>=middlekeygototherightleafpage.

Splittheindexpage.

Keys<middlekeygototheleftindexpage.

Keys>middlekeygototherightindexpage.

Themiddlekeygoestothenext(higherlevel)index.

IFthenextlevelindexpageisfull,continuesplittingtheindexpages.

B

B+TreeInsert

违者

Insertkey28

Insertkey70

Insertkey95

B+TreeRotation

违者

B+treescanincorporaterotationtoreducethenumberofpagesplits.

Arotationoccurswhenaleafpageisfull,butoneofitssiblingpagesisnotfull.

Ratherthansplittingtheleafpage,wemovearecordtoitssibling,adjustingtheindicesasnecessary.Typically,theleftsiblingischeckedfirst(ifitexists)andthentherightsibling.

Insertkey70

B+TreeDeletion 违者

FillFactor

50%

TreeDeletion

违者

LeafPage

BelowFillFactor

IndexPage

BelowFillFactor

Action

No

No

Deletetherecordfromtheleafpage.Arrangekeysinascendingordertofillvoid.

Ifthekeyofthedeletedrecordappearsintheindexpage,usethenextkeytoreceit.

Yes

No

Combinetheleafpageanditssibling.Changetheindexpagetoreflectthechange.

Yes

Yes

binetheleafpageanditssibling.

2.Adjusttheindexpagetoreflectthechange.binetheindexpagewithitssibling.

Continuecombiningindexpagesuntilyoureachapagewiththe

correctfillfactororyoureachtherootpage.

B+

B+TreeDeletion

违者

Deletekey70

Deletekey25

Deletekey60

B+TreeIndexinMySQ 违者

B+TreeIndex

InnoDBStorageEngine

MyISAMStorageEngine

B+TreeIndex 违者

B+TreeIndex

Clusteredindex

Secondaryindex(Nonclusteredindex)

Clusteredindex

Leafpagestorewholerecord

Secondaryindex

Leafpagestorerowidentifier

B+TreeHeight

IO

Performance

Disk

Randomread

Sequentialread

B+Treeindex 违者

ClusteredVSSecondary

Clusteredindexkey=4bytes

Secondaryindexkey=4bytes

Keypointer=6bytes

Averagerowlength=300bytes

Pagesize=16K=16384bytes

Averagenodeoccupancy=70%(bothforleafandindexpage)

Fan-outforclusteredindex=16384*70%/(4+6)=1000

Fan-outforsecondaryindex=16384*70%/(4+6)=1000

Averagerowperpageforclusteredindex=16384*70%/300=35

Averagerowperpageforclusteredindex=16384*70%/(4+6)=1000

H

ClusteredIndex

SecondaryIndex

2

1000*35=35,000

1000*1000=1,000,000

3

(1000)2*35=35,000,000

(1000)2*1000=1,000,000,000

4

(1000)3*35=35,000,000,000

(1000)3*1000=1,000,000,000,000

B+TreeIndexinInnoD 违者

IOT

ClusteredIndex

Leafpagestoreallrowdata

SecondaryIndex

Leafpagestorekey&primarykeyinfo

Bookmarklookup

16Kperpage

HighFanout

B+TreeIndexinInnoD 违者

B+TreeIndexinInnoD

CREATETABLEUserInfo(

useridINTNOTNULLAUTO_INCREMENT,

usernameVARCHAR(30),registdateDATETIME,

VARCHAR(50),

PRIMARYKEY(userid),

UNIQUEKEYidx_username(username),KEYidex_registdate(registdate)

);

违者

CREATETABLE

idx_username_constraint(usernameVARCHAR(30),PRIMARYKEY(username)

);

CREATETABLEUserInfo(

useridINTNOTNULLAUTO_INCREMENT,

usernameVARCHAR(30),registdateDATETIME,

VARCHAR(50),

PRIMARYKEY(userid)

);

CREATETABLE

idx_username(

useridINTNOTNULL,usernameVARCHAR(30),PRIMARYKEY

(username,userid)

);

CREATETABLE

idx_registdate(

useridINTNOTNULL,registdateDATETIME),PRIMARYKEY

(registdate,userid)

);

B+TreeIndexinInnoD 违者

INSERToperation

STARTTRANSACTION;

INSERTINTOUserInfovalues(aaa,bbb,ccc);INSERTINTOidx_username_constraint(bbb);INSERTINTOidx_username(bbb,aaa);INSERTINTOidx_registdate(ccc,aaa);COMMIT;

B+TreeIndexinMyISA 违者

HeapTable

Allindexisnonclustered/secondary

ThedifferencebetweenPrimaryKeyandKeyisnotNULLandunique

Leafpagestoredataaddress

1Kperpage

B+TreeIndexinMyISA 违者

HowtouseB+TreeIn 违者

Cardinality

NotuseB+Treeindexsituation

Compoundindex

Coveringindex

Indexwithincludedcolumn

Cardinality 违者

Thecountofnoneuniquerecord

Highselectivity

UsingB+treetoaccesslessrecord

SELECT*FROMstudentWHERE=’M’

lowselectivity

SELECT*FROMstudentWHEREname=‘DavidJiang’

Namehighselectivity

NotuseB+Treeindex 违者

SecondaryIndex

Needlotsofrandomread

Accessmorerows(20%+)

Optimizerchoosesequentialreadinstead

SELECT*FROMorderdetails

WHEREorderid>10000andorderid<102000;

CompoundIndex 违者

Indexwithmulticolumn

(a,b)

a:1,1,2,2,3,3

(a,b):(1,1),(1,2),(2,1),(2,4),(3,1),(3,2)

b:1,2,1,4,1,2

CompoundIndexAdvan 违者

Canbeused

SELECT*FROMtWHEREa=?

SELECT*FROMtWHEREa=?ANDb=?

Cannotbeused

SELECT*FROMtWHEREb=?

Sort(a，b),nofilesortneed

SELECT*FROMtwherea=?ORDERBYb

IndexCoverage

CoveringIndex

违者

Getdata(result)throughsecondaryindex

Nobookmarklookupneeded

Usingindexhint

（primarykey1，primarykey2，…，key1，key2，…）

SELECTkey2FROMtableWHEREkey1=xxx；

SELECTprimarykey2,key2FROMtableWHEREkey1=xxx；

SELECTprimarykey1,key2FROMtableWHEREkey1=xxx；

SELECTprimarykey1,primarykey2，key2FROMtableWHEREkey1=xxx；

（a，b）compoundindex

Canquerycolumn（a）or（a，b）

Generally,cannotqueryon(b)

However

SELECTCOUNT(1)FROMbuy_logWHEREbuy_date>='2011-01-01'

ANDbuy_date<'2011-02-01

(userid,buy_date)compoundindex

CREATETABLEUserInfo(

useridINTNOTNULLAUTO_INCREMENT,

usernameVARCHAR(30),registdateDATETIME,

VARCHAR(50),

PRIMARYKEY(userid),

UNIQUEKEYidx_username(username, ),KEYidex_registdate(registdate)

);

Indexwithincludedco 违者

SELECT FROMUserInfoWHEREusername=‘David’

Needbookmarklookup,twotreesneedtobelookupHowtooptimizequerylikethis?

Indexwithincludedco 违者

Howaboutcoveringindex(username, )

However,wedonotneed tobesort

Weneedindexusername,butalsoincludecolumn

Useextraspacetoimproveperformance

Indexwithincludedco 违者

CREATETABLEUserInfo(

useridINTNOTNULLAUTO_INCREMENT,

usernameVARCHAR(30),registdateDATETIME,

VARCHAR(50),

PRIMARYKEY(userid),

UNIQUEKEYidx_username(usernaKEYidex_registdate(registdate)

);

BEGIN;

INSERTINTOUs