Database index principle

1 Index:
Index is similar to the directory of the book, is mainly used to improve query efficiency, according to the conditions query, the first query the index, and then through the index to find the relevant data, the index is equivalent to recorded a keyword assigned to a different file or file Lane different positions, of course, the index itself is through the file saved.
(2) the type of index There are two basic index structure is a sequential index is sorted in accordance with the order of values ??(the value of the file inside, that is, its construction of the index field values, the order on the index file inside ), a hash index is the value assigned to the average number of hash buckets, positioning through a hash function.
2.1 The sequential index being indexed according to a certain order, then such an index called the clustered index. Otherwise known as non-clustered index.
If the field is indexed each has an index value corresponding thereto, then this index is called dense index, otherwise called a sparse index.
Order index is divided into two categories, single-stage index (do not use) and multi-level index (usually a B + tree, heavy use).
Single-stage index all index fields and the corresponding file location arranged according to the order, such an index to find them more slowly, because it is stored in the order, you can use binary search, but overall efficiency is not high, This index is the most basic index, generally do not have, the Oracle there does not seem to support such an index.
Multi-level index is actually above the the coupled index (sparse index) in a single-stage index, that is, the index pointing to the index, secondary index also be coupled at the tertiary index can add, add to the last uppermost only one node (the root node), it becomes a tree.
We often hear the concept of the B + tree is almost The purpose of this tree and red-black tree, but also to try to keep the balance of the tree, of course, the red-black tree is a binary tree, but the B + tree is not a binary tree below the node can have multiple children node, database developers will set a maximum number of child nodes, this value is not too small, so the B + tree in general relatively chunky, lanky red-black tree.
About B + tree insertion, deletion, will involve a number of algorithms to maintain the balance of the tree, not detailed here. ORACLE default index of this structure.
If you often need two fields at the same time AND query, then use two separate index is better to create a composite index, usually two separate index database can only use one of the composite index because the index itself corresponds to two fields on the efficiency will be greatly improved.
2.2 hash index
The second index is called the hash index is an index hash function to locate, but rarely used alone hash index, but is hash file organization with more.
Hash file organization is based on a key through a hash calculation corresponding records are placed in the same tank, in which case the same key corresponding record must be in the same file, thus reducing the file read the frequency and to improve the efficiency.
Hash index is based on the hash code of the corresponding key to find the final index entries, in fact, almost the same, and the B-tree, which is an index on the two secondary indexes, I understand hash index sparse index of level or higher, or the barrel too much, efficiency is not high.
2.3 bitmap index
Bitmap index is a special kind of index of the the simple query design one for more than one field, the scope is relatively small, only applies to the field value is fixed and the kind of values ??that a few, such as gender, only male and female, or level, status, etc., and only at the same query on multiple fields in order to realize the advantages of a bitmap.
The basic idea of the bitmap of each condition with a 0 or 1 to indicate if there are five records, sex is male, female, male, male, female, If you use a bitmap index creates two bitmaps corresponding male 01001 of 10110 and the corresponding woman, doing what good is it, that is the same time, more of this type of field and or or query, you can use the results bit by bit or to direct get .

B + tree most commonly used, the performance is not bad, for a range query and single-valued query. In particular range queries have to use the B + tree in this order it.
HASH if only single-valued query words faster than B + tree a little faster, but Oracle does not seem to support the HASH index only supports the HASH table space.
Bitmap usage is very limited, only a few can be used to determine the true for using this index (value type is small and requires complex queries), or to establish a lot of bitmap on the significance Nothing.

Posted by databasesql