04 索引

来源:https://www.cnblogs.com/itiancong/p/18023061
-Advertisement-
Play Games

索引:為了提高數據查詢的效率,就像書的目錄一樣。 索引的常見模型 哈希表 圖中,User2 和 User4 根據身份證號算出來的值都是 N,後面還跟了一個鏈表。假設,這時候你要查 ID_card_n2 對應的名字是什麼,處理步驟就是:首先,將 ID_card_n2 通過哈希函數算出 N;然後,按順序 ...


索引:為了提高數據查詢的效率,就像書的目錄一樣。

索引的常見模型


哈希表

圖中,User2 和 User4 根據身份證號算出來的值都是 N,後面還跟了一個鏈表。假設,這時候你要查 ID_card_n2 對應的名字是什麼,處理步驟就是:首先,將 ID_card_n2 通過哈希函數算出 N;然後,按順序遍歷,找到 User2。

需要註意的是,圖中四個 ID_card_n 的值並不是遞增的,好處是增加新的 User 時速度會很快,只需要往後追加。缺點是,因為不是有序的,所以哈希索引做區間查詢的速度是很慢的。****

哈希表結構適用於只有等值查詢的場景

有序數組

有序數組在等值查詢和範圍查詢場景中的性能就都非常優秀。

要查 ID_card_n2 對應的名字,用二分法就可以快速得到,時間複雜度是 O(log(N))。同時很顯然,這個索引結構也支持範圍查詢。

僅僅看查詢效率,有序數組就是最好的數據結構。但是,在需要更新數據的時候就麻煩了,往中間插入一個記錄就必須得挪動後面所有的記錄,成本太高。

所以,有序數組索引只適用於靜態存儲引擎

N 叉樹

二叉搜索樹的特點是:父節點左子樹所有結點的值小於父節點的值,右子樹所有結點的值大於父節點的值。

如果你要查 ID_card_n2 的話,圖中的搜索順序就是按照 UserA -> UserC -> UserF -> User2 這個路徑得到。時間複雜度是 O(log(N))

為了維持 O(log(N)) 的查詢複雜度,需要保持這棵樹是平衡二叉樹。為了做這個保證,更新的時間複雜度也是 O(log(N))

二叉樹是搜索效率最高的,但是實際上大多數的資料庫存儲卻並不使用二叉樹。其原因是,索引不止存在記憶體中,還要寫到磁碟上


InnoDB 的索引模型

在 MySQL 中,索引是在存儲引擎層實現的。

InnoDB 使用了 B+ 樹索引模型,每一個索引在 InnoDB 裡面對應一棵 B+ 樹

一個主鍵列為 ID 的表,表中有欄位 k,並且在 k 上有索引。

表中 R1~R5 的 (ID,k) 值分別為 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6),兩棵樹的示例示意圖如下。

InnoDB 的索引組織結構

根據葉子節點的內容,索引類型分為主鍵索引和非主鍵索引。

  • 主鍵索引的葉子節點存的是整行數據。在 InnoDB 里,主鍵索引也被稱為聚簇索引(clustered index)。
  • 非主鍵索引的葉子節點內容是主鍵的值。在 InnoDB 里,非主鍵索引也被稱為二級索引(secondary index)。

基於主鍵索引和普通索引的查詢區別?

  • select * from T where ID=500,即主鍵查詢方式,則只需要搜索 ID 這棵 B+ 樹;
  • select * from T where k=5,即普通索引查詢方式,需要先搜索 k 索引樹,得到 ID 值為 500,再到 ID 索引樹搜索一次。這個過程稱為回表

基於非主鍵索引的查詢需要多掃描一棵索引樹,因此在應用中應該儘量使用主鍵查詢


索引維護

  • 主鍵長度越小,普通索引的葉子節點就越小,普通索引占用的空間也就越小
  • 有業務邏輯的欄位做主鍵,則往往不容易保證有序插入,寫數據成本相對較高。

從性能和存儲空間方面考量,自增主鍵往往是更合理的選擇。

同時適合用業務欄位直接做主鍵的場景是:

  • 只有一個索引;
  • 該索引必須是唯一索引。

由於沒有其他索引,所以也就不用考慮其他索引的葉子節點大小的問題。

這時候優先考慮“儘量使用主鍵查詢”原則,直接將這個索引設置為主鍵,可以避免每次查詢需要搜索兩棵樹。


問:對於 InnoDB 表 T,如果你要重建索引 k,你的兩個 SQL 語句可以這麼寫:

alter table T drop index k;
alter table T add index(k);

如果你要重建主鍵索引,也可以這麼寫:

alter table T drop primary key;
alter table T add primary key(id);

對於上面這兩個重建索引的作法,說出你的理解。

答:為什麼要重建索引。索引可能因為刪除,或者頁分裂等原因,導致數據頁有空洞,重建索引的過程會創建一個新的索引,把數據按順序插入,重建索引使得頁面的利用率最高,也就是索引更緊湊、更省空間

重建索引 k 的做法是合理的,可以達到省空間的目的。但是,重建主鍵的過程不合理。

不論是刪除主鍵還是創建主鍵,都會將整個表重建。所以連著執行這兩個語句的話,第一個語句就白做了。這兩個語句,你可以用這個語句代替 : alter table T engine=InnoDB。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Gif演示 分解步驟 1,使用組件DataGridView 2,使用DataSource來控製表格展示的數據來源(註意:來源需要是DataTable類型) 3,需要用到非同步線程。如果是不控制數據源的話,需要使用UI安全線程;(使用Control.Invoke或Control.BeginInvoke方 ...
  • 今天同事發開中遇到了一個代碼性能優化的問題,原本需求是:從一個資料庫中查詢某個表數據,存放到datatable中,然後遍歷datatable,看這些數據在另一個資料庫的表中是否存在,存在的話就要更新,不存在就要插入。 就這個需求本身來說很簡單,但是隨著數據量的增大,之前通過迴圈遍歷的方式就出現了性能 ...
  • 網關: 一:apisix doc:https://apisix.apache.org/zh/docs/apisix/getting-started/README/ github:https://github.com/apache/apisix 二:Kong github:https://github ...
  • 在實際應用中,富文本隨處可見,如留言板,聊天軟體,文檔編輯,特定格式內容等,在WPF開發中,如何實現富文本編輯呢?本文以一個簡單的小例子,簡述如何通過RichTextBox實現富文本編輯功能,主要實現複製,剪切,粘貼,撤銷,重做,保存,打開,文本加粗,斜體,下劃線,刪除線,左對齊,居中對齊,右對齊,... ...
  • 概述:通過FluentFTP庫,輕鬆在.NET中實現FTP功能。支持判斷、創建、刪除文件夾,判斷文件是否存在,實現上傳、下載和刪除文件。簡便而強大的FTP操作,提升文件傳輸效率。 在.NET中,使用FluentFTP庫可以方便地實現FTP的相關功能。以下是判斷文件夾是否存在、文件夾的創建和刪除、判斷 ...
  • 概述:在C#多線程編程中,合理終止線程是關鍵挑戰。通過標誌位或CancellationToken,實現安全、協作式的線程終止,確保在適當時機終止線程而避免資源泄漏。 應用場景: 在C#多線程編程中,有時需要終止正在運行的線程,例如在用戶取消操作、程式關閉等情況下。 思路: 線程終止通常涉及到合作式終 ...
  • internal class Program { static List<string> list=new List<string>() { "A","B","C","D","A","B","C","D" }; static string hiddenEle1 = string.Empty;//第一 ...
  • 痞子衡嵌入式半月刊: 第 92 期 這裡分享嵌入式領域有用有趣的項目/工具以及一些熱點新聞,農曆年分二十四節氣,希望在每個交節之日準時發佈一期。 本期刊是開源項目(GitHub: JayHeng/pzh-mcu-bi-weekly),歡迎提交 issue,投稿或推薦你知道的嵌入式那些事兒。 上期回顧 ...
一周排行
    -Advertisement-
    Play Games
  • 下麵是一個標準的IDistributedCache用例: public class SomeService(IDistributedCache cache) { public async Task<SomeInformation> GetSomeInformationAsync (string na ...
  • 這個庫提供了在啟動期間實例化已註冊的單例,而不是在首次使用它時實例化。 單例通常在首次使用時創建,這可能會導致響應傳入請求的延遲高於平時。在註冊時創建實例有助於防止第一次Request請求的SLA 以往我們要在註冊的時候實例單例可能會這樣寫: //註冊: services.AddSingleton< ...
  • 最近公司的很多項目都要改單點登錄了,不過大部分都還沒敲定,目前立刻要做的就只有一個比較老的項目 先改一個試試手,主要目標就是最短最快實現功能 首先因為要保留原登錄方式,所以頁面上的改動就是在原來登錄頁面下加一個SSO登錄入口 用超鏈接寫的入口,頁面改造後如下圖: 其中超鏈接的 href="Staff ...
  • Like運算符很好用,特別是它所提供的其中*、?這兩種通配符,在Windows文件系統和各類項目中運用非常廣泛。 但Like運算符僅在VB中支持,在C#中,如何實現呢? 以下是關於LikeString的四種實現方式,其中第四種為Regex正則表達式實現,且在.NET Standard 2.0及以上平... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他們的程式記憶體會偶發性暴漲,自己分析了下是非托管記憶體問題,讓我幫忙看下怎麼回事?哈哈,看到這個dump我還是非常有興趣的,居然還有這種游戲幣自助機類型的程式,下次去大玩家看看他們出幣的機器後端是不是C#寫的?由於dump是linux上的程式,剛好win ...
  • 前言 大家好,我是老馬。很高興遇到你。 我們為 java 開發者實現了 java 版本的 nginx https://github.com/houbb/nginx4j 如果你想知道 servlet 如何處理的,可以參考我的另一個項目: 手寫從零實現簡易版 tomcat minicat 手寫 ngin ...
  • 上一次的介紹,主要圍繞如何統一去捕獲異常,以及為每一種異常添加自己的Mapper實現,並且我們知道,當在ExceptionMapper中返回非200的Response,不支持application/json的響應類型,而是寫死的text/plain類型。 Filter為二方包異常手動捕獲 參考:ht ...
  • 大家好,我是R哥。 今天分享一個爽飛了的面試輔導 case: 這個杭州兄弟空窗期 1 個月+,面試了 6 家公司 0 Offer,不知道問題出在哪,難道是杭州的 IT 崩盤了麽? 報名面試輔導後,經過一個多月的輔導打磨,現在成功入職某上市公司,漲薪 30%+,955 工作制,不咋加班,還不捲。 其他 ...
  • 引入依賴 <!--Freemarker wls--> <dependency> <groupId>org.freemarker</groupId> <artifactId>freemarker</artifactId> <version>2.3.30</version> </dependency> ...
  • 你應如何運行程式 互動式命令模式 開始一個互動式會話 一般是在操作系統命令行下輸入python,且不帶任何參數 系統路徑 如果沒有設置系統的PATH環境變數來包括Python的安裝路徑,可能需要機器上Python可執行文件的完整路徑來代替python 運行的位置:代碼位置 不要輸入的內容:提示符和註 ...