Tree-Structured Indexing

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/23

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

24 Terms

1
New cards

Tree-Structured Indexing

Uses a tree (usually B+ Tree) to organize index entries for efficient search

2
New cards

B+ Tree

Multi-level balanced tree where all data entries are at the leaf level

3
New cards

B+ Tree Internal Nodes

Contain only search keys and pointers to children

4
New cards

B+ Tree Leaf Nodes

Contain all actual data entries (key + pointer or record)

5
New cards

Order (d) of B+ Tree

Each internal node has between d and 2d keys (d+1 to 2d+1 pointers)

6
New cards

B+ Tree Height

Kept small (log base d of N) to allow fast lookups

7
New cards

B+ Tree Search Complexity

O(log n) where n is the number of entries

8
New cards

B+ Tree Insertion

Insert key at leaf; may cause node to split and propagate up

9
New cards

B+ Tree Deletion

Delete key; may cause merge or redistribution

10
New cards

B+ Tree Range Queries

Supported efficiently via leaf node linked list

11
New cards

Clustered B+ Tree

Data file is sorted in the same order as the B+ Tree index

12
New cards

Unclustered B+ Tree

Data file order differs from index; index points to records

13
New cards

Sparse Index

Points to first record of each page; used with sorted files

14
New cards

Dense Index

Has an index entry for every record

15
New cards

Multi-level Index

Index on top of another index to reduce size and improve performance

16
New cards

Search Key in B+ Tree

Attribute(s) used for sorting and lookup in index

17
New cards

Fan-Out (f)

Number of pointers in an internal B+ Tree node; high fan-out = low height

18
New cards

Overflow Page

Used when too many records have the same search key value

19
New cards

Primary Tree Index

B+ Tree built on primary key (unique, sorted)

20
New cards

Secondary Tree Index

B+ Tree built on non-primary attributes; may have duplicates

21
New cards

Composite Key Index

B+ Tree where key consists of multiple attributes

22
New cards

Advantages of B+ Tree

Supports efficient equality and range queries, updates, and sorted access

23
New cards

Difference from B Tree

B+ Tree stores data only in leaves; B Tree stores data in all nodes

24
New cards