[MAINFRAME, IBM MAINFRAMES TUTORIAL, JCL TUTORIAL, VSAM TUTORIAL, COBOL TUTORIAL, DB2 TUTORIAL, CICS] DB2 Basics : Indexes

[Quasar Chunawala]

DB2 Basics : Indexes

An index is a data-structure that exists physically on the disk. The index is usually defined on one or more columns of a table. It has the ordered column and pointers to rows in the table. Indexes are the fastest way to access DB2 data. Indexes reduce search-time.

Fig. Searching a value k in the Index

An index is essentially a B+ Tree. It has a root page, internal nodes and leaf pages. Each node has records containing two fields - the key and pointer(ROWID) to other nodes. The leaf nodes have no children; instead they house keys and pointers to data pages. B+ Trees are used in most filesystems and relational database products like IBM DB2, MS-SQL Server, Oracle, Sybase etc. to create indexes on data for efficient retrieval.

Let's say we are searching for a value k in the B+ Tree. Starting at the root page, we'll walk our way through the index and reach a leaf containing the value k. At each node, we determine which internal pointer we should follow. An internal B+ Tree node has at most b(in the above example b=3) children.

--
Posted By Quasar Chunawala to MAINFRAME, IBM MAINFRAMES TUTORIAL, JCL TUTORIAL, VSAM TUTORIAL, COBOL TUTORIAL, DB2 TUTORIAL, CICS at 3/07/2014 11:32:00 AM

[Quasar Chunawala]

DB2 Basics : Indexes

An index is a data-structure that exists physically on the disk. The index is usually defined on one or more columns of a table. It has the ordered column and pointers to rows in the table. Indexes are the fastest way to access DB2 data. Indexes reduce search-time.

Fig. Searching a value k in the Index

An index is essentially a B+ Tree. It has a root page, internal nodes and leaf pages. Each node has records containing two fields - the key and pointer(ROWID) to other nodes. The leaf nodes have no children; instead they house keys and pointers to data pages. B+ Trees are used in most filesystems and relational database products like IBM DB2, MS-SQL Server, Oracle, Sybase etc. to create indexes on data for efficient retrieval.

Let's say we are searching for a value k in the B+ Tree. Starting at the root page, we'll walk our way through the index and reach a leaf containing the value k(assume k=28). At each node, we determine which internal pointer we should follow. An internal B+ Tree node has at most b(in the above example b=3) children.

Imagine every node represent a range e.g. the root node represents 1<=key<=100, the blue node stands for 1<=key<=20, the yellow 21<=key<=40 and so forth. We compare k with the root node records. If k < 20, search the blue node. If 21<=k<=40, search the yellow node. If 41<=k<=60, search the green node. We follow the pointer to the yellow-node and the above steps applied recursively. Searching a tree with 3 leaf nodes takes 1 comparision, with 9 leaf nodes, takes 2 comparisions, with 27 leaf nodes takes 3 comparisions, with n leaf nodes requires log₃ n comparisions. An index with b branches would require log_b n comparisions. Searching a value in index requires logarithmic time.

Inserts and PCTFREE

On index creation, LOADs and REORGs, DB2 reserves empty space for future INSERTs on every page. PCTFREE, a percentage of the total page-size reserves space for row overflows on all pages. Say, PCTFREE=10 of a 4K page would be 400 bytes area. As time goes by, INSERTs add entries whereas DELETE pseudo-deletes the index entries. A few index holes are good, into which newly inserted rows can go. When an INSERT happens, DB2 finds the candidate page affected. Based on the newly INSERTed row's key, an index hole may be reused, otherwise its added to the overflow area. If there isn't any room for the additional row to fit, DB2 will split the page into two equal groups(V10 can adapt and split asymmetric for better sequential insert performance).