SQL Indexing - Revision history

Suhridk: /* Introduction */

2014-10-03T12:07:52Z

Introduction

2014-10-02T15:01:29Z

Introduction

2014-10-02T15:01:05Z

2014-10-02T14:56:24Z

Introduction

2014-10-02T14:55:51Z

Introduction

2014-10-02T12:35:07Z

Introduction

2014-10-02T12:34:54Z

Introduction

2014-10-02T12:34:43Z

Introduction

2014-10-02T12:34:02Z

Introduction

2014-10-02T12:33:08Z

Introduction

← Older revision		Revision as of 12:07, 3 October 2014
Line 14:		Line 14:
	* Traversing a B-Tree is efficient. Tree depth grows logarithmically compared to the number of indexes.		* Traversing a B-Tree is efficient. Tree depth grows logarithmically compared to the number of indexes.
	[[File:btree-index.jpg]]		[[File:btree-index.jpg]]
		+	* However, an index leaf node can contain multiple entries for the same index. Perhaps even across leaf nodes. So after tree traversal, the DB has to scan the index leaf nodes. So query can be slow even if there is an index on the column.

@@ Line 13: / Line 13: @@
 * This is the Balanced Tree : B-Tree. The branch nodes store the max value of the index leaf node. The root node in turn points to the branch node.
 * Traversing a B-Tree is efficient. Tree depth grows logarithmically compared to the number of indexes.
-[[File:btree-index.jpg|frameless|500px|From :http://use-the-index-luke.com]]
+[[File:btree-index.jpg]]

@@ Line 11: / Line 11: @@
 [[File:index-leaf-nodes.jpg|frameless|500px|From :http://use-the-index-luke.com]]
 * The Index Leaf nodes however are stored in an arbitrary order on the disk - not according to logical order. Therefore the DB needs a second data structure to find the index leaf nodes quickly.
-* This is the Balanced Tree : B-Tree. The Branch nodes store
+* This is the Balanced Tree : B-Tree. The branch nodes store the max value of the index leaf node. The root node in turn points to the branch node.
+* Traversing a B-Tree is efficient. Tree depth grows logarithmically compared to the number of indexes.
-http://use-the-index-luke.com/img/fig01_02_tree_structure.en.svg
+[[File:btree-index.jpg|frameless|500px|From :http://use-the-index-luke.com]]

← Older revision		Revision as of 14:56, 2 October 2014
Line 13:		Line 13:
	* This is the Balanced Tree : B-Tree. The Branch nodes store		* This is the Balanced Tree : B-Tree. The Branch nodes store

−	http://~~upload~~.~~wikimedia.org~~/~~wikipedia~~/~~mediawiki/b/bc/Wiki~~.~~png~~	+	http://use-the-index-luke.com/img/fig01_02_tree_structure.en.svg

← Older revision		Revision as of 14:55, 2 October 2014
Line 10:		Line 10:
	* Doubly linked list enables DB to read indexes forwards and backwards. Index leaf nodes store the indexes in a DB block or page. The blocks are logically stored in the doubly linked list.		* Doubly linked list enables DB to read indexes forwards and backwards. Index leaf nodes store the indexes in a DB block or page. The blocks are logically stored in the doubly linked list.
	[[File:index-leaf-nodes.jpg\|frameless\|500px\|From :http://use-the-index-luke.com]]		[[File:index-leaf-nodes.jpg\|frameless\|500px\|From :http://use-the-index-luke.com]]
		+	* The Index Leaf nodes however are stored in an arbitrary order on the disk - not according to logical order. Therefore the DB needs a second data structure to find the index leaf nodes quickly.
		+	* This is the Balanced Tree : B-Tree. The Branch nodes store
		+
		+	http://upload.wikimedia.org/wikipedia/mediawiki/b/bc/Wiki.png

@@ Line 9: / Line 9: @@
 * The DB combines two data structures for providing indexing - doubly linked lists and search trees.
 * Doubly linked list enables DB to read indexes forwards and backwards. Index leaf nodes store the indexes in a DB block or page. The blocks are logically stored in the doubly linked list.
-[[File:index-leaf-nodes.jpg|frameless|500px]]
+[[File:index-leaf-nodes.jpg|frameless|500px|From :http://use-the-index-luke.com]]