If you have a book about dogs and you want to find an information about let's say, German Shepherds, you could of course flip through all the pages of the book and find what you are looking for - but this of course is time consuming and not very fast.
Another option is that, you could just go to the Index section of the book and then find what you are looking for by using the Name of the entity you are looking ( in this instance, German Shepherds) and also looking at the page number to quickly find what you are looking for.
In Database, the page number is referred to as a pointer which directs the database to the address on the disk where entity is located. Using the same German Shepherd analogy, we could have something like this (“German Shepherd”, 0x77129) where 0x77129 is the address on the disk where the row data for German Shepherd is stored.
In short, an index is a data structure that stores the values for a specific column in a table so as to speed up query search.
所以现在数据库将使用索引来查找名为 John 的员工 因为索引可能会按字母顺序排序 用户名。 而且，因为它是排序的，所以意味着搜索一个名字 速度要快得多，因为所有以“J”开头的名字都是正确的 在索引中彼此相邻！
Simple Description!
The index is nothing but a data structure that stores the values for a specific column in a table. An index is created on a column of a table.
Example: We have a database table called User with three columns – Name, Age and Address. Assume that the User table has thousands of rows.
Now, let’s say that we want to run a query to find all the details of any users who are named 'John'. If we run the following query:
SELECT * FROM User
WHERE Name = 'John'
The database software would literally have to look at every single row in the User table to see if the Name for that row is ‘John’. This will take a long time.
This is where index helps us: index is used to speed up search queries by essentially cutting down the number of records/rows in a table that needs to be examined.
How to create an index:
CREATE INDEX name_index
ON User (Name)
An index consists of column values(Eg: John) from one table, and those values are stored in a data structure.
So now the database will use the index to find employees named John because the index will presumably be sorted alphabetically by the Users name. And, because it is sorted, it means searching for a name is a lot faster because all names starting with a “J” will be right next to each other in the index!
Now, let’s say that we want to run a query to find all the details of any employees who are named ‘Abc’?
SELECT * FROM Employee
WHERE Employee_Name = 'Abc'
What would happen without an index?
Database software would literally have to look at every single row in the Employee table to see if the Employee_Name for that row is ‘Abc’. And, because we want every row with the name ‘Abc’ inside it, we can not just stop looking once we find just one row with the name ‘Abc’, because there could be other rows with the name Abc. So, every row up until the last row must be searched – which means thousands of rows in this scenario will have to be examined by the database to find the rows with the name ‘Abc’. This is what is called a full table scan
How a database index can help performance
The whole point of having an index is to speed up search queries by essentially cutting down the number of records/rows in a table that need to be examined. An index is a data structure (most commonly a B- tree) that stores the values for a specific column in a table.
How does B-trees index work?
The reason B- trees are the most popular data structure for indexes is due to the fact that they are time efficient – because look-ups, deletions, and insertions can all be done in logarithmic time. And, another major reason B- trees are more commonly used is because the data that is stored inside the B- tree can be sorted. The RDBMS typically determines which data structure is actually used for an index. But, in some scenarios with certain RDBMS’s, you can actually specify which data structure you want your database to use when you create the index itself.
How does a hash table index work?
The reason hash indexes are used is because hash tables are extremely efficient when it comes to just looking up values. So, queries that compare for equality to a string can retrieve values very fast if they use a hash index.
For instance, the query we discussed earlier could benefit from a hash index created on the Employee_Name column. The way a hash index would work is that the column value will be the key into the hash table and the actual value mapped to that key would just be a pointer to the row data in the table. Since a hash table is basically an associative array, a typical entry would look something like “Abc => 0x28939″, where 0x28939 is a reference to the table row where Abc is stored in memory. Looking up a value like “Abc” in a hash table index and getting back a reference to the row in memory is obviously a lot faster than scanning the table to find all the rows with a value of “Abc” in the Employee_Name column.
The disadvantages of a hash index
Hash tables are not sorted data structures, and there are many types of queries which hash indexes can not even help with. For instance, suppose you want to find out all of the employees who are less than 40 years old. How could you do that with a hash table index? Well, it’s not possible because a hash table is only good for looking up key value pairs – which means queries that check for equality
What exactly is inside a database index? So, now you know that a database index is created on a column in a table, and that the index stores the values in that specific column. But, it is important to understand that a database index does not store the values in the other columns of the same table. For example, if we create an index on the Employee_Name column, this means that the Employee_Age and Employee_Address column values are not also stored in the index. If we did just store all the other columns in the index, then it would be just like creating another copy of the entire table – which would take up way too much space and would be very inefficient.
How does a database know when to use an index? When a query like “SELECT * FROM Employee WHERE Employee_Name = ‘Abc’ ” is run, the database will check to see if there is an index on the column(s) being queried. Assuming the Employee_Name column does have an index created on it, the database will have to decide whether it actually makes sense to use the index to find the values being searched – because there are some scenarios where it is actually less efficient to use the database index, and more efficient just to scan the entire table.
What is the cost of having a database index?
It takes up space – and the larger your table, the larger your index. Another performance hit with indexes is the fact that whenever you add, delete, or update rows in the corresponding table, the same operations will have to be done to your index. Remember that an index needs to contain the same up to the minute data as whatever is in the table column(s) that the index covers.
As a general rule, an index should only be created on a table if the data in the indexed column will be queried frequently.
The first time I read this it was very helpful to me. Thank you.
Since then I gained some insight about the downside of creating indexes: if you write into a table (UPDATE or INSERT) with one index, you have actually two writing operations in the file system. One for the table data and another one for the index data (and the resorting of it (and - if clustered - the resorting of the table data)). If table and index are located on the same hard disk this costs more time. Thus a table without an index (a heap) , would allow for quicker write operations. (if you had two indexes you would end up with three write operations, and so on)
However, defining two different locations on two different hard disks for index data and table data can decrease/eliminate the problem of increased cost of time. This requires definition of additional file groups with according files on the desired hard disks and definition of table/index location as desired.
Another problem with indexes is their fragmentation over time as data is inserted. REORGANIZE helps, you must write routines to have it done.
In certain scenarios a heap is more helpful than a table with indexes,
e.g:- If you have lots of rivalling writes but only one nightly read outside business hours for reporting.
Also, a differentiation between clustered and non-clustered indexes is rather important.
索引只是一种数据结构，可以更快地搜索数据库中的特定列。 该结构通常是 B 树或哈希表，但也可以是任何其他逻辑结构。
An index is just a data structure that makes the searching faster for a specific column in a database. This structure is usually a b-tree or a hash table but it can be any other logic structure.
Consider a "Book" of 1000 pages, divided by 10 Chapters, each section with 100 pages.
Simple, huh?
Now, imagine you want to find a particular Chapter that contains a word "Alchemist". Without an index page, you have no other option than scanning through the entire book/Chapters. i.e: 1000 pages.
This analogy is known as "Full Table Scan" in database world.
But with an index page, you know where to go! And more, to lookup any particular Chapter that matters, you just need to look over the index page, again and again, every time. After finding the matching index you can efficiently jump to that chapter by skipping the rest.
But then, in addition to actual 1000 pages, you will need another ~10 pages to show the indices, so totally 1010 pages.
Thus, the index is a separate section that stores values of indexed column + pointer to the indexed row in a sorted order for efficient look-ups.
Field name Data type Size on disk
id (Primary key) Unsigned INT 4 bytes
firstName Char(50) 50 bytes
lastName Char(50) 50 bytes
emailAddress Char(100) 100 bytes
When data is stored on disk-based storage devices, it is stored as blocks of data. These blocks are accessed in their entirety, making them the atomic disk access operation. Disk blocks are structured in much the same way as linked lists; both contain a section for data, a pointer to the location of the next node (or block), and both need not be stored contiguously.
Due to the fact that a number of records can only be sorted on one field, we can state that searching on a field that isn’t sorted requires a Linear Search which requires (N+1)/2 block accesses (on average), where N is the number of blocks that the table spans. If that field is a non-key field (i.e. doesn’t contain unique entries) then the entire tablespace must be searched at N block accesses.
Whereas with a sorted field, a Binary Search may be used, which has log2 N block accesses. Also since the data is sorted given a non-key field, the rest of the table doesn’t need to be searched for duplicate values, once a higher value is found. Thus the performance increase is substantial.
What is indexing?
Indexing is a way of sorting a number of records on multiple fields. Creating an index on a field in a table creates another data structure which holds the field value, and a pointer to the record it relates to. This index structure is then sorted, allowing Binary Searches to be performed on it.
The downside to indexing is that these indices require additional space on the disk since the indices are stored together in a table using the MyISAM engine, this file can quickly reach the size limits of the underlying file system if many fields within the same table are indexed.
How does it work?
Firstly, let’s outline a sample database table schema;
Field name Data type Size on disk
id (Primary key) Unsigned INT 4 bytes
firstName Char(50) 50 bytes
lastName Char(50) 50 bytes
emailAddress Char(100) 100 bytes
Note: char was used in place of varchar to allow for an accurate size on disk value. This sample database contains five million rows and is unindexed. The performance of several queries will now be analyzed. These are a query using the id (a sorted key field) and one using the firstName (a non-key unsorted field).
Example 1 - sorted vs unsorted fields
Given our sample database of r = 5,000,000 records of a fixed size giving a record length of R = 204 bytes and they are stored in a table using the MyISAM engine which is using the default block size B = 1,024 bytes. The blocking factor of the table would be bfr = (B/R) = 1024/204 = 5 records per disk block. The total number of blocks required to hold the table is N = (r/bfr) = 5000000/5 = 1,000,000 blocks.
A linear search on the id field would require an average of N/2 = 500,000 block accesses to find a value, given that the id field is a key field. But since the id field is also sorted, a binary search can be conducted requiring an average of log2 1000000 = 19.93 = 20 block accesses. Instantly we can see this is a drastic improvement.
Now the firstName field is neither sorted nor a key field, so a binary search is impossible, nor are the values unique, and thus the table will require searching to the end for an exact N = 1,000,000 block accesses. It is this situation that indexing aims to correct.
Given that an index record contains only the indexed field and a pointer to the original record, it stands to reason that it will be smaller than the multi-field record that it points to. So the index itself requires fewer disk blocks than the original table, which therefore requires fewer block accesses to iterate through. The schema for an index on the firstName field is outlined below;
Field name Data type Size on disk
firstName Char(50) 50 bytes
(record pointer) Special 4 bytes
Note: Pointers in MySQL are 2, 3, 4 or 5 bytes in length depending on the size of the table.
Example 2 - indexing
Given our sample database of r = 5,000,000 records with an index record length of R = 54 bytes and using the default block size B = 1,024 bytes. The blocking factor of the index would be bfr = (B/R) = 1024/54 = 18 records per disk block. The total number of blocks required to hold the index is N = (r/bfr) = 5000000/18 = 277,778 blocks.
Now a search using the firstName field can utilize the index to increase performance. This allows for a binary search of the index with an average of log2 277778 = 18.08 = 19 block accesses. To find the address of the actual record, which requires a further block access to read, bringing the total to 19 + 1 = 20 block accesses, a far cry from the 1,000,000 block accesses required to find a firstName match in the non-indexed table.
When should it be used?
Given that creating an index requires additional disk space (277,778 blocks extra from the above example, a ~28% increase), and that too many indices can cause issues arising from the file systems size limits, careful thought must be used to select the correct fields to index.
Since indices are only used to speed up the searching for a matching field within the records, it stands to reason that indexing fields used only for output would be simply a waste of disk space and processing time when doing an insert or delete operation, and thus should be avoided. Also given the nature of a binary search, the cardinality or uniqueness of the data is important. Indexing on a field with a cardinality of 2 would split the data in half, whereas a cardinality of 1,000 would return approximately 1,000 records. With such a low cardinality the effectiveness is reduced to a linear sort, and the query optimizer will avoid using the index if the cardinality is less than 30% of the record number, effectively making the index a waste of space.
发布评论
评论（7）
只需将数据库索引视为一本书的索引即可。
如果您有一本关于狗的书，并且想要查找有关德国牧羊犬的信息，您当然可以翻阅该书的所有页面并找到您要查找的内容 - 但这当然很耗时，而且不方便。非常快。
另一种选择是，您可以转到本书的索引部分，然后使用您正在查找的实体的名称（在本例中为德国牧羊犬）并查看页码来查找您要查找的内容。快速找到您要找的东西。
在数据库中，页号被称为指针，它将数据库指向实体所在磁盘上的地址。 使用相同的德国牧羊犬类比，我们可以得到类似这样的内容（“德国牧羊犬”，0x77129），其中
0x77129是磁盘上存储德国牧羊犬行数据的地址。简而言之，索引是一种存储表中特定列的值以加快查询搜索的数据结构。
Just think of Database Index as Index of a book.
If you have a book about dogs and you want to find an information about let's say, German Shepherds, you could of course flip through all the pages of the book and find what you are looking for - but this of course is time consuming and not very fast.
Another option is that, you could just go to the Index section of the book and then find what you are looking for by using the Name of the entity you are looking ( in this instance, German Shepherds) and also looking at the page number to quickly find what you are looking for.
In Database, the page number is referred to as a pointer which directs the database to the address on the disk where entity is located. Using the same German Shepherd analogy, we could have something like this (“German Shepherd”, 0x77129) where
0x77129is the address on the disk where the row data for German Shepherd is stored.In short, an index is a data structure that stores the values for a specific column in a table so as to speed up query search.
简单描述！
索引只不过是一种存储表中特定列的值的数据结构。 索引是在表的列上创建的。
示例：我们有一个名为
User的数据库表，其中包含三列 -Name、Age和Address。 假设User表有数千行。现在，假设我们要运行一个查询来查找名为“John”的任何用户的所有详细信息。
如果我们运行以下查询：
数据库软件实际上必须查看
User表中的每一行，以查看该行的Name是否为“John”。 这将需要很长时间。这就是
索引帮助我们的地方：索引用于通过实质上减少表中需要检查的记录/行数来加速搜索查询。如何创建索引：
索引由一个表中的列值（例如：John）组成，这些值存储在数据结构中>。Simple Description!
The index is nothing but a data structure that stores the values for a specific column in a table. An index is created on a column of a table.
Example: We have a database table called
Userwith three columns –Name,AgeandAddress. Assume that theUsertable has thousands of rows.Now, let’s say that we want to run a query to find all the details of any users who are named 'John'.
If we run the following query:
The database software would literally have to look at every single row in the
Usertable to see if theNamefor that row is ‘John’. This will take a long time.This is where
indexhelps us: index is used to speed up search queries by essentially cutting down the number of records/rows in a table that needs to be examined.How to create an index:
An
indexconsists of column values(Eg: John) from one table, and those values are stored in a data structure.现在，假设我们要运行一个查询来查找名为“Abc”的任何员工的所有详细信息？
如果没有索引会发生什么？
数据库软件实际上必须查看 Employee 表中的每一行，以查看该行的 Employee_Name 是否为“Abc”。 而且，因为我们希望每一行中都包含名称为“Abc”的行，所以一旦找到名为“Abc”的行，我们就不能停止查找，因为可能还有其他行的名称为“Abc”强>。 因此，必须搜索直到最后一行的每一行 - 这意味着在这种情况下，数据库必须检查数千行才能找到名为“Abc”的行。 这就是所谓的全表扫描
数据库索引如何提高性能
拥有索引的全部目的是通过从本质上减少索引的数量来加快搜索查询的速度。表中需要检查的记录/行。 索引是一种数据结构（最常见的是 B 树），用于存储表中特定列的值。
B 树索引如何工作？
B 树是最流行的索引数据结构，因为它们具有时间效率 - 因为查找、删除和插入都可以在对数时间内完成。 而且，B 树更常用的另一个主要原因是 B 树中存储的数据可以排序。 RDBMS 通常确定索引实际使用的数据结构。 但是，在某些使用某些 RDBMS 的情况下，您实际上可以在创建索引本身时指定希望数据库使用哪种数据结构。
哈希表索引如何工作？
使用哈希索引的原因是哈希表在查找值时非常高效。 因此，如果使用哈希索引，比较字符串是否相等的查询可以非常快速地检索值。
例如，我们之前讨论的查询可以受益于在 Employee_Name 列上创建的哈希索引。 哈希索引的工作方式是，列值将成为哈希表的键，映射到该键的实际值将只是指向表中行数据的指针。 由于哈希表基本上是一个关联数组，因此典型的条目看起来类似于“Abc =>; 0x28939”，其中 0x28939 是对内存中存储 Abc 的表行的引用。 在哈希表索引中查找像“Abc”这样的值并获取对内存中该行的引用显然比扫描表以查找 Employee_Name 列中值为“Abc”的所有行要快得多。
哈希索引的缺点
哈希表不是排序的数据结构，有很多类型的查询哈希索引甚至无法提供帮助。 例如，假设您想找出所有 40 岁以下的员工。 如何使用哈希表索引做到这一点？ 嗯，这是不可能的，因为哈希表只适合查找键值对 - 这意味着检查相等性的查询
数据库索引中到底有什么？
现在您知道数据库索引是在表中的列上创建的，并且该索引将值存储在该特定列中。 但是，重要的是要了解数据库索引不会将值存储在同一表的其他列中。 例如，如果我们在 Employee_Name 列上创建索引，这意味着 Employee_Age 和 Employee_Address 列值不会也存储在该索引中。 如果我们只是将所有其他列存储在索引中，那么就像创建整个表的另一个副本一样 - 这会占用太多空间并且效率非常低。
数据库如何知道何时使用索引？
当运行像“SELECT * FROM Employee WHERE Employee_Name = 'Abc'”这样的查询时，数据库将检查正在查询的列上是否有索引。 假设 Employee_Name 列确实创建了索引，数据库将必须决定使用索引来查找正在搜索的值是否真的有意义 - 因为在某些情况下使用数据库索引实际上效率较低，并且扫描整个表更高效。
拥有数据库索引的成本是多少？
它占用空间 - 并且表越大，索引就越大。 索引对性能的另一个影响是，每当您在相应表中添加、删除或更新行时，都必须对索引执行相同的操作。 请记住，索引需要包含与索引所覆盖的表列中的数据相同的最新数据。
作为一般规则，只有当索引列中的数据被频繁查询时才应在表上创建索引。
另请参阅
Now, let’s say that we want to run a query to find all the details of any employees who are named ‘Abc’?
What would happen without an index?
Database software would literally have to look at every single row in the Employee table to see if the Employee_Name for that row is ‘Abc’. And, because we want every row with the name ‘Abc’ inside it, we can not just stop looking once we find just one row with the name ‘Abc’, because there could be other rows with the name Abc. So, every row up until the last row must be searched – which means thousands of rows in this scenario will have to be examined by the database to find the rows with the name ‘Abc’. This is what is called a full table scan
How a database index can help performance
The whole point of having an index is to speed up search queries by essentially cutting down the number of records/rows in a table that need to be examined. An index is a data structure (most commonly a B- tree) that stores the values for a specific column in a table.
How does B-trees index work?
The reason B- trees are the most popular data structure for indexes is due to the fact that they are time efficient – because look-ups, deletions, and insertions can all be done in logarithmic time. And, another major reason B- trees are more commonly used is because the data that is stored inside the B- tree can be sorted. The RDBMS typically determines which data structure is actually used for an index. But, in some scenarios with certain RDBMS’s, you can actually specify which data structure you want your database to use when you create the index itself.
How does a hash table index work?
The reason hash indexes are used is because hash tables are extremely efficient when it comes to just looking up values. So, queries that compare for equality to a string can retrieve values very fast if they use a hash index.
For instance, the query we discussed earlier could benefit from a hash index created on the Employee_Name column. The way a hash index would work is that the column value will be the key into the hash table and the actual value mapped to that key would just be a pointer to the row data in the table. Since a hash table is basically an associative array, a typical entry would look something like “Abc => 0x28939″, where 0x28939 is a reference to the table row where Abc is stored in memory. Looking up a value like “Abc” in a hash table index and getting back a reference to the row in memory is obviously a lot faster than scanning the table to find all the rows with a value of “Abc” in the Employee_Name column.
The disadvantages of a hash index
Hash tables are not sorted data structures, and there are many types of queries which hash indexes can not even help with. For instance, suppose you want to find out all of the employees who are less than 40 years old. How could you do that with a hash table index? Well, it’s not possible because a hash table is only good for looking up key value pairs – which means queries that check for equality
What exactly is inside a database index?
So, now you know that a database index is created on a column in a table, and that the index stores the values in that specific column. But, it is important to understand that a database index does not store the values in the other columns of the same table. For example, if we create an index on the Employee_Name column, this means that the Employee_Age and Employee_Address column values are not also stored in the index. If we did just store all the other columns in the index, then it would be just like creating another copy of the entire table – which would take up way too much space and would be very inefficient.
How does a database know when to use an index?
When a query like “SELECT * FROM Employee WHERE Employee_Name = ‘Abc’ ” is run, the database will check to see if there is an index on the column(s) being queried. Assuming the Employee_Name column does have an index created on it, the database will have to decide whether it actually makes sense to use the index to find the values being searched – because there are some scenarios where it is actually less efficient to use the database index, and more efficient just to scan the entire table.
What is the cost of having a database index?
It takes up space – and the larger your table, the larger your index. Another performance hit with indexes is the fact that whenever you add, delete, or update rows in the corresponding table, the same operations will have to be done to your index. Remember that an index needs to contain the same up to the minute data as whatever is in the table column(s) that the index covers.
As a general rule, an index should only be created on a table if the data in the indexed column will be queried frequently.
See also
我第一次读到这篇文章对我来说非常有帮助。 谢谢。
从那时起，我对创建索引的缺点有了一些认识：
如果您使用一个索引写入表（
UPDATE或INSERT），则实际上在文件系统中进行了两次写入操作。 一种用于表数据，另一种用于索引数据（及其排序（以及 - 如果是集群 - 表数据的排序））。 如果表和索引位于同一硬盘上，则会花费更多时间。 因此，没有索引（堆）的表将允许更快的写入操作。 （如果您有两个索引，则最终会进行三个写入操作，依此类推）但是，在两个不同的硬盘上为索引数据和表数据定义两个不同的位置可以减少/消除时间成本增加的问题。 这需要定义附加文件组以及所需硬盘上的相应文件，并根据需要定义表/索引位置。
索引的另一个问题是随着数据的插入，它们会随着时间的推移而产生碎片。
REORGANIZE有帮助，您必须编写例程来完成它。在某些情况下，堆比带有索引的表更有帮助，
例如： - 如果您有大量竞争性写入，但只有在工作时间外每晚读取一次以进行报告。
此外，聚集索引和非聚集索引之间的区别也相当重要。
帮助我：- 聚集索引和非聚集索引实际上意味着什么？
The first time I read this it was very helpful to me. Thank you.
Since then I gained some insight about the downside of creating indexes:
if you write into a table (
UPDATEorINSERT) with one index, you have actually two writing operations in the file system. One for the table data and another one for the index data (and the resorting of it (and - if clustered - the resorting of the table data)). If table and index are located on the same hard disk this costs more time. Thus a table without an index (a heap) , would allow for quicker write operations. (if you had two indexes you would end up with three write operations, and so on)However, defining two different locations on two different hard disks for index data and table data can decrease/eliminate the problem of increased cost of time. This requires definition of additional file groups with according files on the desired hard disks and definition of table/index location as desired.
Another problem with indexes is their fragmentation over time as data is inserted.
REORGANIZEhelps, you must write routines to have it done.In certain scenarios a heap is more helpful than a table with indexes,
e.g:- If you have lots of rivalling writes but only one nightly read outside business hours for reporting.
Also, a differentiation between clustered and non-clustered indexes is rather important.
Helped me:- What do Clustered and Non clustered index actually mean?
索引只是一种数据结构，可以更快地搜索数据库中的特定列。 该结构通常是 B 树或哈希表，但也可以是任何其他逻辑结构。
An index is just a data structure that makes the searching faster for a specific column in a database. This structure is usually a b-tree or a hash table but it can be any other logic structure.
经典示例“书籍索引”
考虑一本 1000 页的“书”，分为 10 章，每节 100 页。
很简单吧？
现在，假设您想要查找包含单词“炼金术士”的特定章节。 如果没有索引页，您除了扫描整本书/章节之外别无选择。 即：1000 页。
这个类比在数据库领域被称为“全表扫描”。
但是有了索引页，您就知道该去哪里！ 而且，要查找任何重要的特定章节，您只需每次都一次又一次地查看索引页。 找到匹配的索引后，您可以通过跳过其余部分来有效地跳转到该章节。
但是，除了实际的 1000 页之外，您还需要另外 ~10 页来显示索引，所以总共 1010 页。
学校里的事情很简单，不是吗？ ：P
Classic example "Index in Books"
Consider a "Book" of 1000 pages, divided by 10 Chapters, each section with 100 pages.
Simple, huh?
Now, imagine you want to find a particular Chapter that contains a word "Alchemist". Without an index page, you have no other option than scanning through the entire book/Chapters. i.e: 1000 pages.
This analogy is known as "Full Table Scan" in database world.
But with an index page, you know where to go! And more, to lookup any particular Chapter that matters, you just need to look over the index page, again and again, every time. After finding the matching index you can efficiently jump to that chapter by skipping the rest.
But then, in addition to actual 1000 pages, you will need another ~10 pages to show the indices, so totally 1010 pages.
Things are simple in schools, isn't it? :P
为什么需要它？
当数据存储在基于磁盘的存储设备上时，它被存储为数据块。 这些块被完整地访问，使它们成为原子磁盘访问操作。 磁盘块的结构与链表非常相似； 两者都包含数据部分、指向下一个节点（或块）位置的指针，并且两者不需要连续存储。
由于多条记录只能在一个字段上排序，我们可以说，在未排序的字段上搜索需要线性搜索，这需要
(N+1)/2块访问（平均），其中N是表跨越的块数。 如果该字段是非键字段（即不包含唯一条目），则必须在N块访问中搜索整个表空间。而对于排序字段，可以使用二分搜索，其具有
log2N块访问。 此外，由于数据是根据给定的非键字段进行排序的，因此一旦找到更高的值，就不需要搜索表的其余部分以查找重复值。 因此，性能的提升是显着的。什么是索引？
索引是一种对多个字段上的大量记录进行排序的方法。 在表中的字段上创建索引会创建另一个数据结构，该数据结构保存字段值以及指向与其相关的记录的指针。 然后对该索引结构进行排序，从而允许对其执行二分搜索。
索引的缺点是这些索引需要额外的磁盘空间，因为索引使用 MyISAM 引擎一起存储在表中，如果对同一个表中的许多字段建立索引，则该文件很快就会达到底层文件系统的大小限制。
它是如何工作的？
首先，让我们概述一个示例数据库表架构；
注意：使用 char 代替 varchar 是为了获得准确的磁盘大小值。
此示例数据库包含 500 万行并且未建立索引。 现在将分析几个查询的性能。 这些是使用id（已排序的键字段）的查询和使用firstName（非键未排序字段）的查询。
示例 1 - 排序字段与未排序字段
给定我们的示例数据库，其中包含固定大小的
r = 5,000,000记录，给出记录长度为R = 204字节，它们使用 MyISAM 引擎存储在表中，该引擎使用默认块大小B = 1,024字节。 表的分块系数为每个磁盘块bfr = (B/R) = 1024/204 = 5记录。 保存该表所需的块总数为N = (r/bfr) = 5000000/5 = 1,000,000块。假设 id 字段是关键字段，则对 id 字段进行线性搜索平均需要
N/2 = 500,000块访问才能找到值。 但由于 id 字段也已排序，因此可以进行二分搜索，需要平均log2 1000000 = 19.93 = 20块访问。 我们立即可以看到这是一个巨大的改进。现在，firstName 字段既未排序，也不是关键字段，因此不可能进行二分搜索，而且值也不是唯一的，因此该表需要搜索到末尾以获取精确的
N = 1,000,000块访问。 索引旨在纠正这种情况。鉴于索引记录仅包含索引字段和指向原始记录的指针，因此它会比它指向的多字段记录小。 因此，索引本身比原始表需要更少的磁盘块，因此需要更少的块访问来进行迭代。 firstName 字段上的索引架构概述如下；
注意：MySQL 中的指针长度为 2、3、4 或 5 个字节，具体取决于表的大小。
示例 2 - 索引
给定我们的示例数据库，其中包含
r = 5,000,000记录，索引记录长度为R = 54字节并使用默认块大小B = 1,024字节。 索引的块因子将为每个磁盘块bfr = (B/R) = 1024/54 = 18记录。 保存索引所需的块总数为 N = (r/bfr) = 5000000/18 = 277,778 块。现在，使用 firstName 字段的搜索可以利用索引来提高性能。 这允许对索引进行二分搜索，平均有
log2 277778 = 18.08 = 19块访问。 要找到实际记录的地址，需要进一步进行块访问来读取，总共需要19 + 1 = 20块访问，这与查找所需的 1,000,000 次块访问相去甚远。 em>firstName 在非索引表中匹配。什么时候应该使用它？
鉴于创建索引需要额外的磁盘空间（上例中额外增加了 277,778 个块，增加了约 28%），并且太多的索引可能会导致文件出现问题由于系统大小有限，必须仔细考虑以选择正确的字段来建立索引。
由于索引仅用于加快在记录中搜索匹配字段的速度，因此理所当然，仅用于输出的索引字段在执行插入或删除操作时只会浪费磁盘空间和处理时间，因此应该避免。 另外，考虑到二分搜索的性质，数据的基数或唯一性也很重要。 对基数为 2 的字段建立索引会将数据分成两半，而基数为 1,000 将返回大约 1,000 条记录。 使用如此低的基数，效率会降低为线性排序，并且如果基数小于记录数的 30%，查询优化器将避免使用索引，从而实际上使索引浪费了空间。
Why is it needed?
When data is stored on disk-based storage devices, it is stored as blocks of data. These blocks are accessed in their entirety, making them the atomic disk access operation. Disk blocks are structured in much the same way as linked lists; both contain a section for data, a pointer to the location of the next node (or block), and both need not be stored contiguously.
Due to the fact that a number of records can only be sorted on one field, we can state that searching on a field that isn’t sorted requires a Linear Search which requires
(N+1)/2block accesses (on average), whereNis the number of blocks that the table spans. If that field is a non-key field (i.e. doesn’t contain unique entries) then the entire tablespace must be searched atNblock accesses.Whereas with a sorted field, a Binary Search may be used, which has
log2 Nblock accesses. Also since the data is sorted given a non-key field, the rest of the table doesn’t need to be searched for duplicate values, once a higher value is found. Thus the performance increase is substantial.What is indexing?
Indexing is a way of sorting a number of records on multiple fields. Creating an index on a field in a table creates another data structure which holds the field value, and a pointer to the record it relates to. This index structure is then sorted, allowing Binary Searches to be performed on it.
The downside to indexing is that these indices require additional space on the disk since the indices are stored together in a table using the MyISAM engine, this file can quickly reach the size limits of the underlying file system if many fields within the same table are indexed.
How does it work?
Firstly, let’s outline a sample database table schema;
Note: char was used in place of varchar to allow for an accurate size on disk value.
This sample database contains five million rows and is unindexed. The performance of several queries will now be analyzed. These are a query using the id (a sorted key field) and one using the firstName (a non-key unsorted field).
Example 1 - sorted vs unsorted fields
Given our sample database of
r = 5,000,000records of a fixed size giving a record length ofR = 204bytes and they are stored in a table using the MyISAM engine which is using the default block sizeB = 1,024bytes. The blocking factor of the table would bebfr = (B/R) = 1024/204 = 5records per disk block. The total number of blocks required to hold the table isN = (r/bfr) = 5000000/5 = 1,000,000blocks.A linear search on the id field would require an average of
N/2 = 500,000block accesses to find a value, given that the id field is a key field. But since the id field is also sorted, a binary search can be conducted requiring an average oflog2 1000000 = 19.93 = 20block accesses. Instantly we can see this is a drastic improvement.Now the firstName field is neither sorted nor a key field, so a binary search is impossible, nor are the values unique, and thus the table will require searching to the end for an exact
N = 1,000,000block accesses. It is this situation that indexing aims to correct.Given that an index record contains only the indexed field and a pointer to the original record, it stands to reason that it will be smaller than the multi-field record that it points to. So the index itself requires fewer disk blocks than the original table, which therefore requires fewer block accesses to iterate through. The schema for an index on the firstName field is outlined below;
Note: Pointers in MySQL are 2, 3, 4 or 5 bytes in length depending on the size of the table.
Example 2 - indexing
Given our sample database of
r = 5,000,000records with an index record length ofR = 54bytes and using the default block sizeB = 1,024bytes. The blocking factor of the index would bebfr = (B/R) = 1024/54 = 18records per disk block. The total number of blocks required to hold the index isN = (r/bfr) = 5000000/18 = 277,778blocks.Now a search using the firstName field can utilize the index to increase performance. This allows for a binary search of the index with an average of
log2 277778 = 18.08 = 19block accesses. To find the address of the actual record, which requires a further block access to read, bringing the total to19 + 1 = 20block accesses, a far cry from the 1,000,000 block accesses required to find a firstName match in the non-indexed table.When should it be used?
Given that creating an index requires additional disk space (277,778 blocks extra from the above example, a ~28% increase), and that too many indices can cause issues arising from the file systems size limits, careful thought must be used to select the correct fields to index.
Since indices are only used to speed up the searching for a matching field within the records, it stands to reason that indexing fields used only for output would be simply a waste of disk space and processing time when doing an insert or delete operation, and thus should be avoided. Also given the nature of a binary search, the cardinality or uniqueness of the data is important. Indexing on a field with a cardinality of 2 would split the data in half, whereas a cardinality of 1,000 would return approximately 1,000 records. With such a low cardinality the effectiveness is reduced to a linear sort, and the query optimizer will avoid using the index if the cardinality is less than 30% of the record number, effectively making the index a waste of space.