Types of indexes in database

By sort order

  • ordered - the indices in which the elements are ordered
  • increasing
  • decreasing
  • unordered - indices at which the items are unordered

By data source

  • view indexes
  • expression indices

By influence on the data source

  • clustered index - When defined in a dataset, the physical location of the data is rebuilt according to the structure of the index. The logical structure of the dataset in this case is more of a dictionary than an index. The data in the dictionary is physically ordered, such as alphabetically. Clustered indexes can provide significant improvements in data search performance, even when compared to regular indexes. The performance increase is especially noticeable when working with sequential data.
  • nonclustered index is the most common member of the index family. Unlike clustered, they do not rebuild the physical structure of the dataset, but only organize links to the corresponding records. To identify the required record in the data set, the nonclustered index organizes special pointers, including: information about the identification number of the file in which the record is stored; page identification number of the corresponding data; number of the searched record on the corresponding page; column contents.

By structure

  • B*-trees
  • B+-trees
  • B-trees
  • Hashes

By quantitative composition

  • simple index (index with one key) - one field at a time;
  • composite (multi-key, composite) index - it is built on several fields, the order of their sequence is important;
  • index with included columns - a non-clustered index that additionally contains non-key columns in addition to key columns;
  • master index (index by primary key) is the index key currently under control of the dataset. The dataset cannot be sorted by multiple index keys at the same time. Although, if the same dataset is open simultaneously in several workspaces, then each copy of the dataset may have its own main index assigned.

By content characteristic

  • unique index consists of many unique field values;
  • dense index (NoSQL) - an index at which, each document in the indexed collection corresponds to an entry in the index, even if the document does not have an indexed field.
  • sparse index (NoSQL) - one in which only those documents are presented for which the indexed key has some specific value (exists).
  • spatial index - Optimized for describing geographic locations. It is a multi-key index consisting of latitude and longitude.
  • composite spatial index - an index that includes, in addition to latitude and longitude, some other metadata (for example, tags). But geographic coordinates should come first.
  • full-text (inverted) index - a dictionary that lists all the words and indicates where they occur. In the presence of such an index, it is enough to search for the necessary words in it and then a list of documents in which they are found will be immediately obtained.
  • hash index involves storing not the values themselves, but their hashes, which reduces the size (and, accordingly, increases the processing speed) of indices from large fields. Thus, when making queries using hash indices, the hash of the desired value will not be compared with the field value, but the hash of the desired value with the field hashes. Due to the non-linearity of hash functions, this index cannot be sorted by value, which makes it impossible to use greater/less and "is null" comparisons. In addition, since hashes are not unique, collision resolution methods are used for matching hashes.
  • bitmap index - the bitmap index method is to create separate bitmaps (sequences 0 and 1) for each possible column value, where each bit corresponds to a record with an indexed value, and its value equal to 1 means that the record corresponding to the bit position contains the indexed value for the given column or property.
  • reverse index - B-tree index, but with a reversed key, used mainly for monotonically increasing values (for example, auto-incremental identifier) in OLTP systems in order to remove competition for the last leaf block of the index, since reversing the value causes two adjacent index entries to fall into different index blocks. It cannot be used for range searches.
  • function-based index - index whose keys store the result of user-defined functions. Functional indexes are often built on fields whose values are preprocessed before being compared in an SQL statement. For example, when comparing string data in a case-insensitive manner, the UPPER function is often used. In addition, a functional index can help implement any other missing type of index in a given DBMS.
  • primary index - a unique index over the primary key field.
  • secondary index - an index on other fields (except for the primary key field).
  • XML index is a clipped materialized representation of XML Binary Large Objects (BLOBs) in a column with the xml data type.

By the update mechanism

  • fully rebuildable - when an element is added, the entire index is rebuilt.
  • replenished (balanced) - when adding elements, the index is partially rebuilt (for example, one of the branches) and periodically balanced.

By coverage of indexed content

  • fully covering (full) index - covers the entire contents of the indexed object.
  • partial index is an index built on a portion of a dataset that satisfies a specific condition in the index itself. This index is designed to reduce the size of the index.
  • incremental (delta) index - a small part of the data (delta) is indexed, usually after a certain time. Used for heavy recording. For example, the full index is rebuilt once a day, and the delta index is rebuilt every hour. It is essentially a partial timestamp index.
  • real-time index - a special type of incremental index, characterized by a high speed of construction. Designed for frequently changing data.

Clustered Indexes

  • global index - an index over the entire contents of all database segments (shard).
  • shard index - global index on the shard key field. It is used to quickly determine the segment where data is stored in the process of routing a request in a database cluster.
  • local index - an index on the content of only one database segment.

Read also:


Comments

Post a Comment

Popular posts from this blog

Methods for reading XML in Java

Image
DOM (Document Object Model) - object - reads XML, recreating it in memory in the form of an object structure, while the XML document is represented as a set of tags - nodes. Each node can have an unlimited number of child nodes. Each child can also contain several levels of descendants or none at all. Thus, the result is a kind of tree. Pluses: Easy to program. If there are many objects in XML with cross-references to each other, it is enough to go through the document twice: first time create objects without references and fill in the name-object dictionary, the second time - restore links. If an error occurs in XML, a half-created XML structure remains in memory, which will be automatically destroyed. Suitable for both reading and writing. Minuses: Low speed. Wastes a lot of memory. SAX (Simple API for XML) - event-driven - reads an XML document, responding to emerging events (opening or closing tag, string, attribute) by calling the event handlers provided by the appl...
Read more

XML, well-formed XML and valid XML

Image
XML, the eXtensible Markup Language, is a language with a simple formal syntax, well suited for creating and manipulating documents with programs, and at the same time easy to read and create documents by humans. XML is extensible, it does not fix the markup used in documents, and the developer is free to create markup in accordance with the needs of a particular area, being limited only by the syntax rules of the language. DTD A DTD, Document Type Definition, is a predefined set of rules that defines the relationships between elements and attributes. For example, the DTD for HTML says that the DIV tag must be inside the BODY tag and can appear multiple times, TITLE - in HEAD and only once, and SCRIPT - both there and there as many times as you want. A DTD is usually described directly in the document as a formulation line starting with <!DOCTYPE ... > or in a separate file. Difference between well-formed XML and valid XML Depending on the level of compliance, the document...
Read more

ArrayList and LinkedList in Java, memory usage and speed

Image
How much extra memory is needed when calling ArrayList.add()? If there is enough space in the array to accommodate a new element, then no additional memory is required. Otherwise, a new array is created, 1.5 times larger than the existing one (this is true for JDK above 1.7, in earlier versions the size of the increase is different). How much extra memory is allocated when you call LinkedList.add()? One new instance of the nested Node class is created. How much memory to store one byte primitive in LinkedList? Each LinkedList element stores a link to the previous element, the next element, and a data link. private static class Node<E> { E item; Node<E> next; Node<E> prev; //... } For 32-bit systems, each link is 32 bits (4 bytes). The object (header) of the nested Node class itself takes 8 bytes. 4 + 4 + 4 + 8 = 20 bytes, and since the size of each object in Java is a multiple of 8, so we get 24 bytes. A byte primitive occupies 1 by...
Read more