阿里一面，給了幾條SQL，問需要執(zhí)行幾次樹搜索操作？

前言

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

一、面試官考點之索引是什么？

二、索引有哪些類型類型

數據結構維度

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

物理存儲維度

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

邏輯維度

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

三、面試官考點之為什么選擇B+樹作為索引結構

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

我們寫業(yè)務SQL查詢時，大多數情況下，都是范圍查詢的，如下SQL

select * from employee where age between 18 and 28;

為什么不使用哈希結構？

我們知道哈希結構，類似k-v結構，也就是，key和value是一對一關系。它用于「等值查詢」還可以，但是范圍查詢它是無能為力的哦。

為什么不使用二叉樹呢？

先回憶下二叉樹相關知識啦~ 所謂「二叉樹，特點如下：」

• 每個結點最多兩個子樹，分別稱為左子樹和右子樹。
• 左子節(jié)點的值小于當前節(jié)點的值，當前節(jié)點值小于右子節(jié)點值
• 頂端的節(jié)點稱為根節(jié)點，沒有子節(jié)點的節(jié)點值稱為葉子節(jié)點。

我們腦海中，很容易就浮現(xiàn)出這種二叉樹結構圖：

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

如果二叉樹特殊化為一個鏈表，相當于全表掃描。那么還要索引干嘛呀？因此，一般二叉樹不適合作為索引結構。

為什么不使用平衡二叉樹呢？

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

但是呢：

• 平衡二叉樹插入或者更新時，需要左旋右旋維持平衡，維護代價大
• 如果數量多的話，樹的高度會很高。因為數據是存在磁盤的，以它作為索引結構，每次從磁盤讀取一個節(jié)點，操作IO的次數就多啦。

為什么不使用B樹呢？

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

B樹相對于平衡二叉樹，就可以存儲更多的數據，高度更低。但是最后為甚選擇B+樹呢？因為B+樹是B樹的升級版：

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

四、面試官考點之一次B+樹索引搜索過程

「面試官：」 假設有以下表結構，并且有這幾條數據

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í)行以下的查詢SQL，需要執(zhí)行幾次的樹搜索操作？可以畫下對應的索引結構圖~

select * from Temployee where age=32;

「解析：」 其實這個，面試官就是考察候選人是否熟悉B+樹索引結構圖?？梢韵襻u紫回答~

• 先畫出 idx_age索引的索引結構圖，大概如下：

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';