【正文】 avoids overflow pages by splitting a full bucket when a new data entry is to be added to it. (Duplicates may require overflow pages.) ? Directory to keep track of buckets, doubles periodically. ? Can get large with skewed data。 additional I/O if this does not fit in main memory. Summary (Contd.) ? Linear Hashing avoids directory by splitting buckets roundrobin, and using overflow pages. ? Overflow pages not likely to be long. ? Duplicates handled easily. ? Space utilization could be lower than Extendible Hashing, since splits not concentrated on `dense’ data areas in the early part of a round. ? For hashbased indexes, a skewed data distribution is one in which the hash values of data entries are not uniformly distributed ? Need a good hash function! Indexes in Standards ? SQL92/99/03 does not standardize use of indexes ? (BNF for SQL2022) ? But all DBMS providers support it ? X/OPEN actually standardized CREATE INDEX clause CREATE [UNIQUE] INDEX indexname ON tablename (colname [ASC | DESC] [,colname [ASC | DESC] ,. . .])。 ? ASC|DESC are just there for patibility, have no effect in any DB I know of. ? Index has as key the concatenation of column names ? In the order specified Indexes in Oracle ? Oracle supports mainly B+Tree Indexes ? These are the default, so just use create index? ? No way to ask for clustered directly ? Clustering on PK is available via indexanized tables (IOTs) ? In this case, the RID is different, affecting secondary index performance ? Also “table cluster” for co locating data of tables often joined ? Hashing: via “hash cluster” ? Also a form of hash partitioning supported ? Also supports bitmap indexes ? Hash cluster example? Example Oracle Hash Cluster CREATE CLUSTER trial_cluster (trialno DECIMAL(5,0)) SIZE 1000 HASH IS trialno HASHKEYS 100000。 CREATE TABLE trial ( trialno DECIMAL(5,0) PRIMARY KEY, ...) CLUSTER trial_cluster (trialno)。 ? SIZE should estimate the max storage in bytes of the rows needed for one hash key ? Here HASHKEYS value specifies a limit on the number of unique keys in use, for hash table sizing. Oracle rounds up to a prime, here 100003. This is static hashing. Oracle Hash Index, continued ? For static hashing in general: rule of thumb— ? Estimate the max possible number of keys and double it. This way, about half the hash cells are in use at most. ? The hash cluster is a good choice if queries usually specify an exact trialno value. ? Oracle will also create a Btree index on trialno because it is the PK. But it will use the hash index for equality searches. MySQL Indexes, for InnoDB Engine ? CREATE [UNIQUE] INDEX index_name [index_type] ON tbl_name (index_col_name,...) ? index_col_name: col_name [(length)] [ASC | DESC] ? index_type: USING {BTREE | HASH} ? Syntax allows for hash index, but not supported by InnoDB. ? For InnoDB, index on primary key is clustered. Clustered index on PK: choose your PK wisely ? Available in Oracle and MySQL, as only kind of clustered Btree index. ? Common PKs are ids, arbitrary, not monly used in range queries, so not getting the good from the clustered Btree. ? However, a PK is what we say it is for a table, and doesn’t need to be minimalistic, just a unique identifier. ? So (zipcode, custid) works as a PK and clusters the data by zipcode. Custid is a “ uniquifier” here. ? Then useful range queries on zipcode run fast. ? Typically, data is inserted first, then index is created ? Exception: alternative (1) indexes (of course!) ? Then best to sort first, then load ? How to sort? Use database: load, sort, dump, load for real ? Index bulkloading is a good idea – recall it is much faster ? Delete an index DROP INDEX indexname。 ? Guidelines: ? Create index if you frequently retrieve less than 15% of the table ? To improve join performance, index columns used for joins ? Small tables do not require indexes, except ones for PKs. Indexes in Practice Compare BTree and Hash Indexes ? Dynamic Hash tables have variable insert times ? Worstcase access time amp。 best average access time ? But only useful for equality key lookups ? Note there are bitmap indexes too