数据库索引的底层原理
-
想要了解数据库索引的底层原理,我们就得先了解一种叫树的数据结构,而树中很经典的一种数据结构就是二叉树!所以下面我们就从二叉树到平衡二叉树,再到B-树,最后到B+树来一步一步了解数据库索引底层的原理!
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。二叉树,英译为:Binary tree,它是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树,且有左右之分。
二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。
每个结点都包含一个元素以及n个子树,这里0≤n≤2。左子树和右子树是有顺序的,次序不能任意颠倒。左子树的值要小于父结点,右子树的值要大于父结点。平衡二叉树是一种特殊的二叉树,所以他也满足前面说到的二叉树的两个特性,同时还有一个特性:平衡树(Balance Tree,BT) 指的是,任意节点的子树的高度差都小于等于1。常见的符合平衡树的有,B树(多路平衡搜索树)、AVL树(二叉平衡搜索树)等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低,在完成集合的一系列操作中始终保持平衡,为大型数据库的组织、索引提供了一条新的途径。
它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这棵树始终满足平衡二叉树的几个特性而保持平衡!这样我们的树也不会退化为线性链表了!我们需要查找一个数的时候就能沿着树根一直往下找,这样的查找效率和二分法查找是一样的呢!
还有一种是B-Tree,要注意中间是横杠。一棵m阶的B-Tree有如下特性:每个结点最多m个子结点。除了根结点和叶子结点外,每个结点最少有m/2(向上取整)个子结点。如果根结点不是叶子结点,那根结点至少包含两个子结点。所有的叶子结点都位于同一层。
并且每个结点都包含k个元素(关键字),这里m/2≤k<m,这里m/2向下取整。每个节点中的元素(关键字)从小到大排列。每个元素(关键字)字左结点的值,都小于或等于该元素(关键字)。右结点的值都大于或等于该元素(关键字)。
西南地区IT社群(QQ)
- 云南
- 【昆明网页设计交流吧】243627302
- 【昆明nodejs交流吧】 243626749
- 【VUE】838405306
- 【云南程序员总群】343606807
- 【昆明UI设计】104031254
- 【云南软件外包】15547313
- 贵州
- 【PHP/java源码/站长交流群】55692114
- 四川
- 【成都Java/JavaWeb交流】86669225
- 【vaScript+PHP+MySql】116270060
- 【UI设计/设计交流学习群】135794928
- 重庆
- 【诺基亚 JAVA游戏博物馆】 559479780
- 【PHP,Java,Python,C++接单】 442103442
- 西藏