SQL Server存储引擎
一、遍历索引树的每个节点都是一个页面。索引树有三种类型的节点：根节点、中间节点、叶子节点。(1)根节点与中间节点一样，只包含下一层节点的入口值与入口指针
一、遍历
索引树的每个节点都是一个页面。
索引树有三种类型的节点：根节点、中间节点、叶子节点。
(1) 根节点与中间节点一样，只包含下一层节点的入口值与入口指针，它们称为索引节点；
(2) 叶子节点包含要遍历的数据，服务器空间，对聚集索引而言数据就是表中数据行，对非聚集索引数据是指索引列值和行书签。
索引的遍历总是从根节点开始，即先根遍历，分为两种：索引扫描和索引查找。
(1) 索引扫描，是指从索引树的根节点开始，对叶子节点逐个扫描，直至命中所有满足查找条件的数据；
(2) 索引查找，是指从索引树的根节点开始，按查找值在索引节点中根据路由信息跳转，直至叶子节点以命中数据。
B+树的深度通常小于等于3，计算如下：
以聚集索引为例，简单计算如下：10个INT列宽度总和为40B，假设聚集索引树每一层为二叉，共三层，即2^0+2^1+2^2=1*(1-2^3)/(1-2)=7个页面，4个叶子节点，每个页面8060K可存储8060000/40=201500行，乘以4=806000行，如果是三叉、四叉，那么三层可存储上千万至亿行的数据，当然在数据量达到这个等级时，通常我们会选择表分区，那么B树深度就更不会突破三层了。
所以索引查找的效率是很高的，在查询中应该努力构造索引查找，避免索引扫描。
二、插入
2.1、页空间充足
在已存在数据的表上，创建或重建索引时，可指定填充因子，即在索引树的每个节点上预留一定的空间，供表中后续增加的数据使用。但如果在创建表的时候就创建了索引，并指定了填充因子，这时的填充因子是无用的，数据库系统不会刻意去保留页面的空间。
索引页面有剩余空间的情况如下图：
图1
参考图1，此时向索引树中插入一条索引键值为31的记录，步骤如下：
（1）执行索引键值=31的查找操作，确定该新记录应该插入到叶子节点L2中。
（2）检查L2上是否有足够的空间来存放当前记录，这里假设有足够的空间；
（3）将记录45向后移动，插入索引键值为31的新记录。插入之后，10、30、31、45还是顺序的，香港服务器，如下图：
图2
2.2、页空间不足
参加图2，此时再插入一条索引键值为32的记录，步骤如下：
（1）执行索引键值=32的查找操作，确定该新记录应该插入到叶子节点L2中；
（2）检查L2上是否有足够的空间来存放当前记录，这时发现没有足够的页空间，香港服务器，此时需要进行页面分裂；
（3）向数据库系统申请一个新的页面L4，将L2的一半数据移到L4中，并重新链接叶子的左右节点，如下图：
图3
（4）此时，上层节点也需要生成一个新的叶子节点的指针。这里的上层节点即根节点，如果上层节点没有剩余空间的话，同样也需要进行分裂，这里有剩余空间，如下图：
图4
（5）因为当前记录的键值范围位于页分裂的后一半中，将索引键值为32的新记录插入到L4中，如果键值范围位于前一半，则插入到L2中。如果L4的空间不够存放键值为32的新记录，则L4会继续进行页分裂，这里假设空间足够，插入结束，如下图：
图5
三、删除
3.1、删除叶子节点中的记录
参考图5，删除索引键值为32的记录，步骤如下：
（1）执行索引键值=32的查找操作，确定该记录在L4中；
（2）将索引键值=32的记录标记为虚影，但并不立即释放空间，虚影记录可用于事务回滚、多版本等；
（3）如果此时L4上的虚影记录空间被申请使用，虚影记录就会被擦除；
（4）如果数据页面最后一条记录也被删除，数据页面会被回收；
3.2、删除非叶子节点中的记录
（1）索引节点中的指针被删除时并不是虚影记录，但同样也不释放空间，直到有新的指针插入时，才会进行空间压缩；
（2）堆表中数据行被删除后，页空间不会被回收，即使是空闲分页也还是标识为分配状态，无法被其他对象使用；
注：从理论上讲，在兄弟节点页面空闲空间都小于50%时，应该将兄弟节点合并，即分裂的逆操作，但这样可能带来的后果是更频繁的页面合并、分裂，成本更大，所以在数据库系统中通常不进行页面合并操作，除非rebuild/reorganize索引。
四、更新
4.1、覆盖更新
如果更新操作能够在页内进行原位键值替换，那么就进行覆盖更新。
4.2、非覆盖更新
无法进行覆盖更新时，更新操作被分解为删除和插入操作。
如果非覆盖更新过程中，新的记录比较长，则会在页面分裂的过程中会带来数据行的移动：
（1）聚集索引的移动对非聚集索引没有影响，因为非聚集索引中存储的是聚集索引的键值，分裂并不会改变键值；
（2）堆表中的数据页分裂，会在原记录处留下一个前转指针，以告诉非聚集索引去哪里找新的记录；
所以数据行的移动对非聚集索引都不会带来维护的成本，非聚集索引的维护成本来自书签的变化：
（1）聚集索引的键值发生变化或被删除；
（2）堆表中的数据行被删除。
本文出自 “SQL Server DBA” 博客，请务必保留此出处
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
1387
52
Java how to loop through a folder and get all file names
Mar 29, 2024 pm 01:24 PM
Java is a popular programming language with powerful file handling capabilities. In Java, traversing a folder and getting all file names is a common operation, which can help us quickly locate and process files in a specific directory. This article will introduce how to implement a method of traversing a folder and getting all file names in Java, and provide specific code examples. 1. Use the recursive method to traverse the folder. We can use the recursive method to traverse the folder. The recursive method is a way of calling itself, which can effectively traverse the folder.
PHP glob() function usage example: traverse all files in a specified folder
Jun 27, 2023 am 09:16 AM
Example of using PHPglob() function: Traverse all files in a specified folder In PHP development, it is often necessary to traverse all files in a specified folder to implement batch operation or reading of files. PHP's glob() function is used to achieve this requirement. The glob() function can obtain the path information of all files that meet the conditions in the specified folder by specifying a wildcard matching pattern. In this article, we will demonstrate how to use the glob() function to iterate through all files in a specified folder
In-depth comparison of Java Iterator and Iterable: pros and cons analysis
Feb 19, 2024 pm 04:20 PM
Conceptual differences: Iterator: Iterator is an interface that represents an iterator that obtains values from a collection. It provides methods such as MoveNext(), Current() and Reset(), allowing you to traverse the elements in the collection and operate on the current element. Iterable: Iterable is also an interface, representing an iterable object. It provides the Iterator() method, which returns an Iterator object to facilitate traversing the elements in the collection. Usage: Iterator: To use Iterator, you need to first obtain an Iterator object, and then call the MoveNext() method to move to the next
How to use the os module to traverse files in a directory in Python 3.x
Jul 29, 2023 pm 02:57 PM
How to use the os module to traverse files in a directory in Python3.x In Python, we can use the os module to operate files and directories. The os module is an important module in the Python standard library, providing many operating system-related functions. In this article, we will explain how to use the os module to iterate through all files in a directory. First, we need to import the os module: importos Next, we can use the os.walk() function to walk the directory.
How to implement binary tree traversal using Python
Jun 09, 2023 pm 09:12 PM
As a commonly used data structure, binary trees are often used to store data, search and sort. Traversing a binary tree is one of the very common operations. As a simple and easy-to-use programming language, Python has many methods to implement binary tree traversal. This article will introduce how to use Python to implement pre-order, in-order and post-order traversal of a binary tree. Basics of Binary Trees Before learning how to traverse a binary tree, we need to understand the basic concepts of a binary tree. A binary tree consists of nodes, each node has a value and two child nodes (left child node and right child node
Recursively insert and traverse linked list in C++
Sep 10, 2023 am 09:21 AM
We get the integer values used to form the linked list. The task is to first insert and then traverse the singly linked list using recursive method. Add node recursively at the end if head is NULL → add node to head otherwise add to head (head → next) recursively traverse nodes if head is NULL → exit otherwise print (head → next) Example input −1-2-7-9 -10 output outputstrong>− linked list: 1→2→7→9→10→NULL input−12-21-17-94-18 output− linked list: 12→21→17→94→18→NULL used in the following program The method is as follows In this method, we will use the function to add nodes and traverse the singly linked list and pass
Java Iterator and Iterable: The key to collection traversal, demystified
Feb 20, 2024 am 10:27 AM
Introduction to IteratorIterator is an interface in Java for traversing collections. It provides a set of methods that allow you to access elements in a collection in a sequential manner. You can use Iterator to iterate over collection types such as List, Set, and Map. Demo code: Listlist=newArrayList();list.add("one");list.add("two");list.add("three");Iteratoriterator=list.iterator();while(iter
Java Iterator vs. Iterable: Unlocking the Power of Java Collections
Feb 19, 2024 pm 07:00 PM
In Java, a collection is a collection of elements that provides a unified interface and methods to store, retrieve and operate these elements. Iterator and Iterable are two important Java interfaces that provide a common mechanism for traversing collection elements. The Iterator interface defines hasNext() and next() methods for traversing collections. The hasNext() method is used to check whether there are any untraversed elements in the collection, and the next() method is used to return the current element and move it to the next element. The Iterable interface defines the iterator() method, which returns an Iterator object for traversing the elements in the collection.
