索引的數據結構(b樹,hash)?

阿裏雲問答 2022-01-07 08:08:00 阅读数:925

索引 hash

索引的數據結構(b樹,hash)?




采納答案1:

索引的數據結構和具體存儲引擎的實現有關,在MySQL中使用較多的索引有Hash索引,B+樹索引等,而我們經常使用的InnoDB存儲引擎的默認索引實現為:B+樹索引。對於哈希索引來說,底層的數據結構就是哈希錶,因此在絕大多數需求為單條記錄查詢的時候,可以選擇哈希索引,查詢性能最快;其餘大部分場景,建議選擇BTree索引。

1)B樹索引

mysql通過存儲引擎取數據,基本上90%的人用的就是InnoDB了,按照實現方式分,InnoDB的索引類型目前只有兩種:BTREE(B樹)索引和HASH索引。B樹索引是Mysql數據庫中使用最頻繁的索引類型,基本所有存儲引擎都支持BTree索引。通常我們說的索引不出意外指的就是(B樹)索引(實際是用B+樹實現的,因為在查看錶索引時,mysql一律打印BTREE,所以簡稱為B樹索引)

1.jpg

查詢方式:

主鍵索引區:PI(關聯保存的時數據的地址)按主鍵查詢,

普通索引區:si(關聯的id的地址,然後再到達上面的地址)。所以按主鍵查詢,速度最快

B+tree性質:

1.)n棵子tree的節點包含n個關鍵字,不用來保存數據而是保存數據的索引。

2.)所有的葉子結點中包含了全部關鍵字的信息,及指向含這些關鍵字記錄的指針,且葉子結點本身依關鍵字的大小自小而大順序鏈接。

3.)所有的非終端結點可以看成是索引部分,結點中僅含其子樹中的最大(或最小)關鍵字。

4.)B+ 樹中,數據對象的插入和删除僅在葉節點上進行。

5.)B+樹有2個頭指針,一個是樹的根節點,一個是最小關鍵碼的葉節點。

2)哈希索引

簡要說下,類似於數據結構中簡單實現的HASH錶(散列錶)一樣,當我們在mysql中用哈希索引時,主要就是通過Hash算法(常見的Hash算法有直接定址法、平方取中法、折疊法、除數取餘法、隨機數法),將數據庫字段數據轉換成定長的Hash值,與這條數據的行指針一並存入Hash錶的對應比特置;如果發生Hash碰撞(兩個不同關鍵字的Hash值相同),則在對應Hash鍵下以鏈錶形式存儲。當然這只是簡略模擬圖。

2.jpg


版权声明:本文为[阿裏雲問答]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201070807599057.html