前言

有位朋友去阿里面試，他說(shuō)面試官給了幾條查詢(xún)SQL，問(wèn):需要執(zhí)行幾次樹(shù)搜索操作？我朋友當(dāng)時(shí)是有點(diǎn)懵的，后來(lái)冷靜思考，才發(fā)現(xiàn)就是考索引的幾個(gè)基礎(chǔ)知識(shí)點(diǎn)~~ 本文我們分九個(gè)索引知識(shí)點(diǎn)，一起來(lái)探討一下。如果有不正確的話(huà)，歡迎指出哈，一起學(xué)習(xí)~

一、面試官考點(diǎn)之索引是什么？

二、索引有哪些類(lèi)型類(lèi)型

數(shù)據(jù)結(jié)構(gòu)維度

• B+樹(shù)索引：所有數(shù)據(jù)存儲(chǔ)在葉子節(jié)點(diǎn)，復(fù)雜度為O(logn)，適合范圍查詢(xún)。
• 哈希索引:  適合等值查詢(xún)，檢索效率高，一次到位。
• 全文索引：MyISAM和InnoDB中都支持使用全文索引，一般在文本類(lèi)型char,text,varchar類(lèi)型上創(chuàng)建。
• R-Tree索引: 用來(lái)對(duì)GIS數(shù)據(jù)類(lèi)型創(chuàng)建SPATIAL索引

物理存儲(chǔ)維度

• 聚集索引：聚集索引就是以主鍵創(chuàng)建的索引，在葉子節(jié)點(diǎn)存儲(chǔ)的是表中的數(shù)據(jù)。
• 非聚集索引：非聚集索引就是以非主鍵創(chuàng)建的索引，在葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵和索引列。

邏輯維度

• 主鍵索引：一種特殊的唯一索引，不允許有空值。
• 普通索引：MySQL中基本索引類(lèi)型，允許空值和重復(fù)值。
• 聯(lián)合索引：多個(gè)字段創(chuàng)建的索引，使用時(shí)遵循最左前綴原則。
• 唯一索引：索引列中的值必須是唯一的，但是允許為空值。
• 空間索引：MySQL5.7之后支持空間索引，在空間索引這方面遵循OpenGIS幾何數(shù)據(jù)模型規(guī)則。

三、面試官考點(diǎn)之為什么選擇B+樹(shù)作為索引結(jié)構(gòu)

可以從這幾個(gè)維度去看這個(gè)問(wèn)題，查詢(xún)是否夠快，效率是否穩(wěn)定，存儲(chǔ)數(shù)據(jù)多少，以及查找磁盤(pán)次數(shù)等等。為什么不是哈希結(jié)構(gòu)？為什么不是二叉樹(shù)，為什么不是平衡二叉樹(shù)，為什么不是B樹(shù)，而偏偏是B+樹(shù)呢？

我們寫(xiě)業(yè)務(wù)SQL查詢(xún)時(shí)，大多數(shù)情況下，都是范圍查詢(xún)的，如下SQL

select * from employee where age between 18 and 28;

為什么不使用哈希結(jié)構(gòu)？

我們知道哈希結(jié)構(gòu)，類(lèi)似k-v結(jié)構(gòu)，也就是，key和value是一對(duì)一關(guān)系。它用于「等值查詢(xún)」還可以，但是范圍查詢(xún)它是無(wú)能為力的哦。

為什么不使用二叉樹(shù)呢？

先回憶下二叉樹(shù)相關(guān)知識(shí)啦~ 所謂「二叉樹(shù)，特點(diǎn)如下：」

• 每個(gè)結(jié)點(diǎn)最多兩個(gè)子樹(shù)，分別稱(chēng)為左子樹(shù)和右子樹(shù)。
• 左子節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，當(dāng)前節(jié)點(diǎn)值小于右子節(jié)點(diǎn)值
• 頂端的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)值稱(chēng)為葉子節(jié)點(diǎn)。

我們腦海中，很容易就浮現(xiàn)出這種二叉樹(shù)結(jié)構(gòu)圖：

但是呢，有些特殊二叉樹(shù)，它可能這樣的哦：

如果二叉樹(shù)特殊化為一個(gè)鏈表，相當(dāng)于全表掃描。那么還要索引干嘛呀？因此，一般二叉樹(shù)不適合作為索引結(jié)構(gòu)。

為什么不使用平衡二叉樹(shù)呢？

平衡二叉樹(shù)特點(diǎn)：它也是一顆二叉查找樹(shù)，任何節(jié)點(diǎn)的兩個(gè)子樹(shù)高度最大差為1。所以就不會(huì)出現(xiàn)特殊化一個(gè)鏈表的情況啦。

但是呢：

• 平衡二叉樹(shù)插入或者更新時(shí)，需要左旋右旋維持平衡，維護(hù)代價(jià)大
• 如果數(shù)量多的話(huà)，樹(shù)的高度會(huì)很高。因?yàn)閿?shù)據(jù)是存在磁盤(pán)的，以它作為索引結(jié)構(gòu)，每次從磁盤(pán)讀取一個(gè)節(jié)點(diǎn)，操作IO的次數(shù)就多啦。

為什么不使用B樹(shù)呢？

數(shù)據(jù)量大的話(huà)，平衡二叉樹(shù)的高度會(huì)很高，會(huì)增加IO嘛。那為什么不選擇同樣數(shù)據(jù)量，「高度更矮的B樹(shù)」呢？

B樹(shù)相對(duì)于平衡二叉樹(shù)，就可以存儲(chǔ)更多的數(shù)據(jù)，高度更低。但是最后為甚選擇B+樹(shù)呢？因?yàn)锽+樹(shù)是B樹(shù)的升級(jí)版：

• B+樹(shù)非葉子節(jié)點(diǎn)上是不存儲(chǔ)數(shù)據(jù)的，僅存儲(chǔ)鍵值，而B(niǎo)樹(shù)節(jié)點(diǎn)中不僅存儲(chǔ)鍵值，也會(huì)存儲(chǔ)數(shù)據(jù)。innodb中頁(yè)的默認(rèn)大小是16KB，如果不存儲(chǔ)數(shù)據(jù)，那么就會(huì)存儲(chǔ)更多的鍵值，相應(yīng)的樹(shù)的階數(shù)（節(jié)點(diǎn)的子節(jié)點(diǎn)樹(shù)）就會(huì)更大，樹(shù)就會(huì)更矮更胖，如此一來(lái)我們查找數(shù)據(jù)進(jìn)行磁盤(pán)的IO次數(shù)有會(huì)再次減少，數(shù)據(jù)查詢(xún)的效率也會(huì)更快。
• B+樹(shù)索引的所有數(shù)據(jù)均存儲(chǔ)在葉子節(jié)點(diǎn)，而且數(shù)據(jù)是按照順序排列的，鏈表連著的。那么B+樹(shù)使得范圍查找，排序查找，分組查找以及去重查找變得異常簡(jiǎn)單。

四、面試官考點(diǎn)之一次B+樹(shù)索引搜索過(guò)程

「面試官：」 假設(shè)有以下表結(jié)構(gòu)，并且有這幾條數(shù)據(jù)

CREATE TABLE `employee` (
  `id` int(11) NOT NULL,
  `name` varchar(255) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `date` datetime DEFAULT NULL,
  `sex` int(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_age` (`age`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

insert into employee values(100,'小倫',43,'2021-01-20','0');
insert into employee values(200,'俊杰',48,'2021-01-21','0');
insert into employee values(300,'紫琪',36,'2020-01-21','1');
insert into employee values(400,'立紅',32,'2020-01-21','0');
insert into employee values(500,'易迅',37,'2020-01-21','1');
insert into employee values(600,'小軍',49,'2021-01-21','0');
insert into employee values(700,'小燕',28,'2021-01-21','1');

「面試官：」 如果執(zhí)行以下的查詢(xún)SQL，需要執(zhí)行幾次的樹(shù)搜索操作？可以畫(huà)下對(duì)應(yīng)的索引結(jié)構(gòu)圖~

select * from Temployee where age=32;

「解析：」 其實(shí)這個(gè)，面試官就是考察候選人是否熟悉B+樹(shù)索引結(jié)構(gòu)圖。可以像醬紫回答~

• 先畫(huà)出 idx_age索引的索引結(jié)構(gòu)圖，大概如下：

select * from employee where name like '%杰倫%';

select * from employee where name like '小%' order by age desc;

select * from employee where name like '小%' and age=28 and sex='0';