面试常问-数据库索引实现原理

知识内容：

1.数据库数据储存

2.数据库索引实现

一、数据库数据存储

1.数据库中数据存储形式

数据库中的数据均是存储在数据表中，每个数据库由不同的数据表构成，不同的表存储着不同的数据，这里以用户表为例

一个简单的用户表结构如下：

2.数据库表结构模拟

上述中的用户表用python语法结构可以简化为以下结构：

 1 [
 2     {
 3         "id": 1,
 4         "username": wyb,
 5         "password": xxxxxx,
 6 
 7     },
 8     {
 9         "id": 2,
10         "username": woz,
11         "password": xxxxxx,
12 
13     },
14     {
15         "id": 3,
16         "username": alex,
17         "password": xxxxxx,
18 
19     },
20 ]

注：上述代码中的password字段均为xxxxxx表示密码为加密后的数据

这样的结构实现了对数据库中表结构的模拟，但是这样的结构也存在一定问题：

它是一个包含了 dict 的 list，我们要查找 id 为 n 的元素, 需要从头到尾遍历这个 list 并且比较 id
最坏的情况是 id 为 n 的这个元素根本不存在, 你需要遍历整个 list 才能得到你想要的结果，这样就不能非常快速地根据 id 查找到我们想要的元素，于是后来就有了索引技术

二、数据库索引实现

1.索引介绍

索引定义：索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息

数据库索引是用于提高数据库表的数据访问速度的。

数据库索引的特点：

a）避免进行数据库全表的扫描，大多数情况，只需要扫描较少的索引页和数据页，而不是查询所有数据页。而且对于非聚集索引，有时不需要访问数据页即可得到数据。

b）聚集索引可以避免数据插入操作，集中于表的最后一个数据页面。

c）在某些情况下，索引可以避免排序操作。

2.索引实现原理

索引背后的数据结构基础是B+tree，在这里不细究，只用python的简单数据结构介绍基本的索引实现原理

为了不遍历上面的整个列表，我们将结构改成以下并加上索引表如下：

 1 # 数据库索引实现:
 2 {
 3     '索引': {
 4         'username': {
 5             'wyb': 1,
 6             'woz': 2,
 7         },
 8 
 9     },
10   1: {
11     "id": 1,
12     "username": "wyb",
13     "password": "xxxxxx"
14   },
15   2: {
16     "id": 2,
17     "username": "woz",
18     "password": "xxxxxx"
19   }
20 }

此时通过id查找某个用户时直接使用id值查找即可，若要使用username查找用户，在索引字典中查找相应username对应的id值即可，为数据表中某一项加索引即是向索引字典中加入

这一项的的名字及这一项所有值与id组成的项的字典如上图中的索引下的username