“基礎不是100分考60分，而是建摩天大樓的地基。”

為什么需要索引？

（1）在實際的軟件開發工作的本質都可以抽象為“對數據的存儲和計算”。對應到數據結構和算法中，那“存儲”需要的就是數據結構，“計算”需要的就是算法。
（2）對于存儲的需求，功能上無外乎增刪改查。當存儲的數據很多，性能就會成為這些系統要關注的重點，特別是在存儲相關的基礎系統、中間件中。
（3）“如何節省存儲空間、如何提高數據增刪改查的執行效率”，解決這樣的問題離不開索引

索引的需求定義

對于系統設計需求，一般可以從功能性需求和非功能性需求兩方面來分析

1. 功能性需求

（1）數據是格式化數據還是非格式化數據？
構建索引的原始數據，可分為兩類：

• 一類是結構化數據，如MySQL 中的數據；
• 一類是非結構化數據，如搜索引擎中網頁。非結構化數據，一般需要預處理，提取出查詢關鍵詞，對關鍵詞構建索引。

（2）數據是靜態數據還是動態數據？

• 如果是一組靜態數據，在構建索引時只需考慮查詢效率
• 動態數據構建索引，不僅要考慮索引的查詢效率，在原始數據更新的同時，還需要動態地更新索引

（3）索引存儲在內存還是硬盤？

• 當數據量小時，索引可以存儲在內存中。
• 原始數據量很大時，對應的索引可能也會很大。內存有限，可能需要將索引存儲在磁盤中。
• 第三種情況：一部分存儲在內存，一部分存儲在磁盤，這樣可以兼顧內存消耗和查詢效率。

（4）單值查找還是區間查找？

• 所謂單值查找，也就是根據查詢關鍵詞等于某個值的數據。
• 所謂區間查找，就是查找關鍵詞處于某個區間值的所有數據。不同的應用場景，查詢的需求會多種多樣。

（5）單關鍵詞查找還是多關鍵詞組合查找？

• 對于單關鍵詞的查找，索引構建起來相對簡單。
• 多關鍵詞查詢要分多種情況:
  A：像 MySQL 這種結構化數據的查詢，可以實現針對多個關鍵詞的組合，建立索引；
  B：像搜索引擎這樣的非結構數據的查詢，可以針對單個關鍵詞構建索引，然后通過集合操作，如求并集、求交集等，計算出多個關鍵詞組合的查詢結果。
  不同的場景，不同的原始數據，對于索引的需求也會千差萬別

2. 非功能性需求

（1）不管是存儲在內存中還是磁盤中，索引對存儲空間的消耗不能過大。

• 如果存儲在內存中，索引對占用存儲空間的限制就會非常苛刻
• 如果存儲在硬盤中，也不能掉以輕心，因為有時索引對存儲空間的消耗會超過原始數據

（2）在考慮索引查詢效率的同時，還要考慮索引的維護成本。

• 基于動態數據集合構建的索引要考慮索引的維護成本。因為在原始數據動態增刪改的同時，也需要動態的更新索引。而索引的更新勢必會影響到增刪改操作的性能。

構建索引常用的數據結構有哪些？

如散列表、紅黑樹、跳表、B+ 樹，除此之外，位圖、布隆過濾器可以作為輔助索引，有序數組可以用來對靜態數據構建索引

• 散列表增刪改查操作的時間復雜度是 O(1)，被一些鍵值數據庫用來構建索引，如 Redis、Memcache。這類索引，一般都構建在內存中。

• 紅黑樹是常用的平衡二叉查找樹，數據插入、刪除、查找的時間復雜度是 O(logn)，也非常適合用來構建內存索引。Ext 文件系統中，對磁盤塊的索引，用的就是紅黑樹。

• B+ 樹比起紅黑樹更加適合構建存儲在磁盤中的索引
  （1）B+ 樹是一個多叉樹，對相同個數的數據構建索引，B+ 樹的高度要低于紅黑樹。
  （2）當借助索引查詢數據時，讀取 B+ 樹索引需要的磁盤 IO 次數會更少。
  所以，如 MySQL、Oracle等，大部分關系型數據庫的索引都是用 B+ 樹來實現的

• 跳表也支持快速添加、刪除、查找數據，通過調整索引結點個數和數據個數之間的比例，可以很好地平衡索引對內存的消耗及其查詢效率。Redis 中的有序集合，就是用跳表來構建的

• 布隆過濾器有一定的判錯率，但可以規避它的短處，發揮它的長處
  （1）盡管對于判定存在的數據可能并不存在，但是對于判定不存在的數據是一定不存在
  （2）布隆過濾器有個大特點：內存占用非常少，所以可以針對數據，構建一個布隆過濾器存儲在內存中。
  （3）查詢數據時，如果布隆過濾器判定數據不存在，就不必讀取磁盤中的索引了。對于數據不存在的情況，數據查詢就更加快速了。

• 有序數組也可以被作為索引，如果數據是靜態的只有查詢操作，可以把數據的關鍵詞（查詢用的）抽取出來，組織成有序數組，然后利用二分查找算法來快速查找數據。

筆記整理來源： 王爭 數據結構與算法之美

總結

以上是生活随笔為你收集整理的【数据结构与算法】【算法思想】【算法总结】索引结构的全部內容，希望文章能夠幫你解決所遇到的問題。

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