1.二分查找算法

　　二分查找法的時間復雜度為Ο(log2n)。大家如果有興趣可以去驗證一下這個結果，這里我就不做解釋了。

　　我們具體來感受一下二分查找法有多強大，假設：集合里面有40億個元素，排序方式為從左往右，依次遞增，我們最多需要查找log₂?4000000000? = 32次，就可以在40億個元素里面找到我們需要的元素 。說點題外話：雖然二分查找法很強大，但這并不意味著二分查找法適用于任何場景，因為我們在為業務場景選擇算法時，除了算法的時間復雜度，還要考慮空間復雜度，而且越復雜的程序越是容易發生異常。最主要的是二分查找法只能用于依次遞增或依次遞減的有序集合。

2.二叉查找樹

　　二叉查找樹是采用二分查找法的思維把數據按規則組裝成一個樹形結構。所以平衡二叉樹的深度為Ο(log2n)，即從根節點到離它最遠的葉子節點的距離為Ο(log2n)，二叉查找樹的數據結構如下圖所示(注：本文所有圖片來自其它文章)：

　　

總結平衡二叉樹特點：
（1）非葉子節點最多擁有兩個子節點；
（2）非葉子節值大于左邊子節點、小于右邊子節點；
（3）樹的左右兩邊的層級數相差不會大于1;
（4）沒有值相等重復的節點;

3.索引的數據結構——B+樹

　　數據庫的索引結構采用的是B+樹。B+樹是一種二叉查找樹，而二叉查找樹又是根據二分查找法的思維組裝的一種數據結構。所以，這就是為什么先要介紹二分查找法和二叉查找樹的原因。之前我們已經知道了二分查找法的查找效率很高，為什么不用二叉查找樹作為索引的數據結構呢？難道B+樹的查找速度要比二叉查找樹還要快嗎？當然不是，我們先來了解一下B+樹，

?

　　從上圖可知，一個磁盤塊即為一個節點，并且數據只存放在葉子結點，非葉子節點存放的是磁盤塊的地址，通過磁盤塊的地址找到存放數據的磁盤塊，這樣大大的減少了磁盤的IO操作次數，所以就節省了大量的查找時間。因為程序是在內存里面運行，而數據是放在磁盤塊里面的，尋找磁盤塊的時間遠遠大于程序的運行時間，所以B+樹的主要功能實際是減少磁盤的IO操作次數。

4.總結

　　1.索引可以提高查詢效率，但是因為索引的數據結構是一種二叉查找樹，這就要求這棵樹的結構必須是有規律的，所以，每次進行DML操作的時候，數據庫都要重新去維護這棵樹的結構，這就導致了DML操作時會產生大量的資源開銷。所以，請根據實際業務場景來決定是否使用索引。

　　2.事物型數據庫的索引原理除了B+樹數據結構，還有其它數據結構，但那些數據結構我就沒了解過了。大家如果有興趣可以了解一下。

　　3.除了事物型數據庫，還有一種分析型數據庫，比如數據倉庫，數據集市，這些就涉及到大數據的技術了。

　　4.本來我以為我可以寫好這篇文章，但最后才發現好多地方都解釋得不清楚，請多多包涵！

?

轉載于:https://www.cnblogs.com/heyingquan/p/10712929.html

總結

以上是生活随笔為你收集整理的关于事物型数据库的索引原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。