Shulou(Shulou.com)05/31 Report--

Today, I will talk to you about why database indexes use B+ trees, which may not be well understood by many people. In order to let you know more, Xiaobian summarizes the following contents for you. I hope you can gain something according to this article.

What is the database index?

Index, just like our book catalogue, if a book does not have a catalogue, then you have to find a certain knowledge point, it is naturally quite laborious. The database index plays this role. It tells you where the data is stored on disk, like the number of pages in a directory. So what exactly does the database "catalog" look like?

Common database index has the following three types, the first is the hash table, hash table I believe we are no stranger, we can hash the index field of the database and save it. As long as the hash algorithm is properly designed, we can find a storage address for the corresponding data very quickly, and then we can quickly find the data at the corresponding storage address. So, what are the disadvantages of hash indexing? First of all, the hash table is more suitable for use in memory, but if you want to drop the disk, it is more troublesome, especially when the hash table is expanded, a lot of data on the disk will be modified. Second, hash tables cannot filter an interval.

The second is an array index, similar to the hash table above, but different. Similar to hash indexing, array indexing is also very efficient. To find elements in an ordered array, we only need to perform binary search. But the problem with array indexing is also very obvious, that is, insertion is very troublesome, you insert a new element, you have to move all the elements behind it. Therefore, array indexes are generally only used for static data.

Ordered arrays are said, then the next must be binary tree, we say binary tree is of course binary sort tree, binary sort tree relative to the array, the larger advantage is convenient insertion. However, there is also such a problem, because the index data may exist on the disk, so if the index data exceeds 1000, it may take 10 times to find the final data, and the bottleneck of disk IO is seek and rotation, efficiency will inevitably decrease. Therefore, we want to minimize the number of seek and rotation on disk, so multi-fork trees are widely used in database indexes. The most commonly used tree is the B+ tree.

After reading the above, do you have any further understanding of why database indexes use B+ trees? If you still want to know more knowledge or related content, please pay attention to the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.