# Indexes and Search Trees
## Agenda

Indexes
- Motivation: what are indexes required for?
- Kinds of Indexes
- Primary Index
- Clustered Index
- Secondary (non-clustered) Index
- Multilevel Index
- When to use indexes

Tree Data Structures
- Binary Search Trees (BST)
- B Trees
- Variants: B+ / B* / AVL Trees
## References

### Academic References
1. Avi Silberschatz, Henry F. Korth, S. Sudarshan: [Database System](https://www.db-book.com/) [Concepts](https://www.db-book.com/) [- 7th](https://www.db-book.com/) [edition](https://www.db-book.com/), McGraw-Hill, ISBN 9780078022159.
2. Lecture "[Relational Database Systems 2](http://www.ifis.cs.tu-bs.de/teaching/ss2019/rdb2)" (ifis, TU Braunschweig)
- [Indexing and Access Paths](http://www.ifis.cs.tu-bs.de/sites/default/files/03-Indexing_1.pdf)
- [Trees and Advanced Indexes](http://www.ifis.cs.tu-bs.de/sites/default/files/04-Trees_1.pdf)
3. [Organization and Maintenance of Large Ordered Indexes](http://www.inf.fu-berlin.de/lehre/SS10/DBS-Intro/Reader/BayerBTree-72.pdf) by R. Bayer and E. McCreight. In: Acta Informatica, Vol. 1, Fasc. 3, 1972, pp. 173-189.
- The paper that originally proposed the B-tree family of trees.
### Further Online References
4. [Podcast SE Radio: B+ trees for databases](https://traffic.libsyn.com/secure/seradio/Episode-485-Howard-Chu-on-Btree-Data-Structure-in-Depth.mp3?dest-id=23379)
6. [A Practical Guide to PostgreSQL Indexes](https://learn.percona.com/e3t/Ctc/T5+113/c4R9l04/VWLsyS7XdHF-W1__7yr6CzYRPVBzM2_5gjySxN22w0-T5nR32W50kH_H6lZ3p4N910jMRqjs8pW1Qwcw14MZf1KN5gJphPtNtR-W9d7L9g3sGwv7F7Dj19FczKsW4MnNM34PSKRHW2mcF3g6Jq2hmVs8NW02vhdrfMk3WFjk8dgZW3QFc0w3BnHsnW2Fnjw68PxJD5W5P_35n2z1_6fW7y6Gsp98V8JBN4fjZxyl-M6FW8dB0LY5FWTT3W7f_8kc22wR_SMfxB5FNVPZlN7wF4dRdKWQ8W21G2Ky95xK5zF9h5Td38fcBW15lm8Z74tq38W693ryb1pb-1wW48BJrD66-ZvHVFjK6476TPYRW4BnmhK2fhVq1W2Vk74Y7QhZMXW9m2LVF2wxPw5W4yWs881BpchlVW1QFF7wLTmKW57P5hF8-6NPVW3sYnK82jfmV_W67mkqF6lcdK9f42Gv9b04)
7. [Unlocking the Power of MySQL Indexing: A Beginner’s Guide | by Noran Saber Abdelfattah | Medium](https://medium.com/@noransaber685/unlocking-the-power-of-mysql-indexing-a-beginners-guide-76a58ee9372b)
8. [Indexing and Access Paths](http://www.ifis.cs.tu-bs.de/sites/default/files/03-Indexing_1.pdf)
9. [Trees and Advanced Indexes](http://www.ifis.cs.tu-bs.de/sites/default/files/04-Trees_1.pdf)
10. [Why We Need Indexes for Database Tables](https://towardsdatascience.com/why-we-need-indexes-for-database-tables-25198145a8ca)
11. [How B+Tree Indexes Are Built In A Database?](https://towardsdatascience.com/how-b-tree-indexes-are-built-in-a-database-6f847fb3cfcc)
12. [Anatomie eines SQL Indexes](https://use-the-index-luke.com/de/sql/anatomie)
13. [Efficient retrieval of database records via B+Tree indexes](http://web.csulb.edu/~amonge/classes/common/db/B+TreeIndexes.html)
14. [How to get the best out of your Postgres and Mysql Indexes](https://learn.percona.com/en/performance-optimization-how-to-get-the-best-out-of-your-postgres-and-mysql-indexes)
15. [The Difference Between B-trees and B+trees](https://www.baeldung.com/cs/b-trees-vs-btrees)
16. 14. [MySQL CREATE INDEX command](https://www.mysqltutorial.org/mysql-index/mysql-create-index/)
17. [MySQL USE INDEX Hint](https://www.mysqltutorial.org/mysql-index/mysql-use-index/)
18. [How do database indexes work?](https://www.programmerinterview.com/database-sql/what-is-an-index/)
### Tree animations
19. [B-Tree Visualization](https://www.cs.usfca.edu/~galles/visualization/BTree.html)
20. [Binary Search Tree, AVL Tree - VisuAlgo](https://visualgo.net/en/bst)
21. [File:Binary-search-tree-insertion-animation.gif - Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Binary-search-tree-insertion-animation.gif)
22. [GitHub - vaneela/BST-visualizer](https://github.com/vaneela/BST-visualizer)

## The person behind it
23. [Rudolf Bayer (Informatiker) – Wikipedia](https://de.wikipedia.org/wiki/Rudolf_Bayer_(Informatiker))

## Flashcards

[Indexes - AnkiWeb](https://ankiweb.net/shared/info/1215966305)