资源描述
*,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,2005 Julian Dyke,IndexInternals,Julian Dyke,Independent Consultant,Web Version,juliandyke,2005 Julian Dyke,Agenda,Introduction,Block Structure,Block Compression,Insertion,Deletion,Coalesce/Rebuild,Freelists,Virtual Indexes,2,B*Tree Indexes,Based on modified B*Tree algorithm,Contain branch blocks and leaf blocks,Blocks contain keys and data,Keys maintained in sorted order within blocks,All leaf blocks are at the same depth,All blocks are on average 75%full,3,Index Types,There are several recent variants of B*tree indexes including,Type,Introduced,Bitmap Indexes,7.3.2,Index Organised Table,8.0,Partitioned Indexes,8.0,Reverse Key,8.0,LOB Index,8.0,Compressed,8.1.5,Function-Based Indexes,8.1.5,Descending,8.1.5,Virtual Indexes,8.1.5,Bitmap Join Indexes,9.0.1,4,Limits,Maximum number of B*tree levels is 24,Maximum number of columns is 16 in 7.3 and below;32 in 8.0 and above,Maximum key lengths vary with release and block size,Block Size,8.1.7,9.0.1,9.2.0,2048,758,1526,1478,4096,1578,3166,3118,8192,3218,6446,6398,16384,6498,13006,12958,5,Leaf Blocks,Every index has a least one leaf block,Each leaf block contains 0 or more rows,Each row contains a key and data,Indexes can be unique or non-unique,Leaf row formats differ for unique and non-unique indexes,6,Leaf Block Structure,20 bytes,72 bytes,16 bytes,16 bytes,2 bytes per row,4 bytes,Block Common Header,Transaction Header,Index Header,Index Leaf Header,Index Leaf Rows,Tail,Free Space,Slot Array,Block Size,2 bytes,7,Branch Blocks,Indexes may contain branch blocks,Branch blocks point to other branch blocks or leaf blocks,Branch blocks contain 0 or more rows,Each row has a suffix compressed key and a pointer to the next block,Compressed rows are terminated with 0 xFE byte,8,Branch Block Structure,20 bytes,Block Common Header,Transaction Header,Index Header,Index Branch Header,Index Branch Rows,Tail,Free Space,Slot Array,48 bytes,16 bytes,24 bytes,2 bytes per row,4 bytes,Block Size,2 bytes,9,Branch Blocks,Each block has a pointer to the left hand side of the tree.This is part of the header,A branch block containing N rows points to N+1 blocks.,S,D,E,U,DEN,ENG,SCOSPA,USA,AUSBELCAN,Branch Blocks,Root Block,Leaf Blocks,Level 0,Level 1,Level 2,10,Root Block,Every index has one root block,May be a leaf block or a branch block,Can be an empty leaf block,Always the next block after the segment header in the first extent,Segment Header,RootBlock,.,First Extent,11,BLEVEL versus Height,BLEVEL,is the number of branch block levels in the B*tree,ANALYZE INDEX i1 COMPUTE STATISTICS;,SELECT blevel FROM dba_indexesWHERE index_name=I1;,Height is the total number of levels in the B*tree,ANALYZE INDEX i1 VALIDATE STRUCTURE;,SELECT height FROM index_stats;,Height=,BLEVEL,+1,12,Internal versus External ROWIDs,Internal ROWIDs are used in branch blocks Always 4 bytes.,External ROWIDs are used in leaf blocks,Bytes,Description,6,Local Indexes,8,Cluster Indexes,10,Global Indexes,32,LOB Indexes,In 7.3.4 and below all ROWIDs are 4 bytes,IOTs do not use external ROWIDs,13,Leaf Rows,ROWID,Column 1,FlagByte,LengthByte(s),LockByte,LengthByte(s),Column 2,Unique Index,ROWID,Column 1,FlagByte,LengthByte(s),LockByte,LengthByte(s),Column 2,LengthByte,Non-Unique Index,Unique indexes use one byte per row less than non-unique indexes,Each column has one length byte(128 bytes);two length bytes otherwise,14,Non Unique versus Unique Indexes,SELECT c01,c02FROM t1WHERE c01 IN(SELECT c01 FROM t2);,SELECT STATEMENTMERGE JOINSORT JOINTABLE ACCESS(FULL)T1SORT JOINVIEW OF VW_NSO_1SORT(UNIQUE)TABLE ACCESS(FULL)T2,SELECT STATEMENTNESTED LOOPSTABLE ACCESS(FULL)T1INDEX(UNIQUE SCAN)I2,CREATE INDEX i2 ON t2(c01);,CREATE UNIQUE INDEX i2 ON t2(c01);,Non UniqueIndex,UniqueIndex,15,Non Unique Leaf Rows,All leaf rows are stored in sorted order,For non-unique indexes the ROWID is appended to the key to create a unique key,Keys must be effectively unique so that updates can traverse the B*tree directly to the affected leaf block without requiring a scan,For concatenated indexes allows range scans of prefix columns,16,Non-Unique Leaf Rows,Y,Y,Y,Y,Y,01 41 E9 A5 00 01,01 41 E9 A5 00 02,01 41 E9 A6 00 00,01 41 E9 A6 00 01,01 41 E9 A6 00 02,Y,Y,Y,Y,Y,01 41 E9 A7 00 00,01 41 E9 A7 00 01,01 41 E9 A7 00 02,01 41 E9 A8 00 00,01 41 E9 A8 00 01,Y,Y,Y,Y,Y,01 41 E9 A8 00 02,01 41 E9 A9 00 00,01 41 E9 A9 00 01,01 41 E9 A9 00 02,01 41 E9 AA 00 00,01 41 E9 A8 00 02,Y,01 41 E9 A7,Y,For non-unique indexes ROWIDs may be stored in branch blocks,ROWIDs are suffix compressed where possible,17,Branch Block Compression,Branch block rows are suffix compressed,Number of branch blocks in an index is determined by,Length of index key and data,Number of leaf blocks,Uniqueness of the leading edge of the key,Number of branch blocks affects index height,18,Branch Block Compression,0,0,0,0,0,9,9,9,9,9,9,0,0,0,0,0,9,9,9,9,9,9,0,0,0,0,9,9,9,9,9,9,0,0,0,0,9,9,9,9,9,9,0,0,9,9,9,9,9,9
展开阅读全文